۱/چرا زبان [tex]L=\{ww^R:w\in L(b^{\ast}a^ )\}[/tex] قطعی است؟
(در صورتی که میدونیم [tex]L=\{ww^R:w\in(b^{ } a^{ })^{\ast}\}[/tex] قطعی نیستش.)
سلام ببینید میتونیم اینجوری کار کنیم که ایتدا هر چی b دیدیم تو پشته Push کنیم تا اینکه به a برسیم.از اونجایی که توی این زبان که نوشتید تعداد a ها باید حتما زوج باشه.پس به ازای هر a از رشته w یه a ی متناظر توی [tex]w^R[/tex] هم داریم.
خب پس الان بالای پشته b هستش و a میبینیم،اون a رو Push میکنیم و حالا اگه دوباره a اومد میگیم این a همون a متناظر با قبلی هستش پس a رو از بالای پشته Pop میکنیم حالا اگه دوباره a بیاد چون بالای پشته b هستش میدونیم این a مربوط به w هستش و Push میکنیم حالا بالای پشته a هستش و اگه دوباره a بیاد میدونیم باید همون a متناظر باشه پس Pop میکنیم.اینقد این کارا انجام میدیم تا b بیاد.اگه وقتی b اومد بالای پشته a بودش که غیرقابل قبول هست اون رشته چون میدونیم تعداد a ها فرد بوده(که برای [tex]ww^R[/tex] این اشتباهه) و اگه
بالای پشته b بود یعنی تعداد a ها درست بوده و با هم مطابقت داشتند.حالا به ازای هر b که میبینیم یه b از بالای پشته Pop میکنیم اگه تو انتها که رشته تموم شد پشته خالی بود رشته پذیرفته میشه و در غیر این صورت پذیرفته نمیشه.میبینید که عدم قطعیت تو ماشینمون نداشتیم
ببخشید اگه بد توضیح دادم