(۱۱ دى ۱۳۹۰ ۰۱:۳۸ ب.ظ)miladdn13 نوشته شده توسط:  چرا زبان a^n b^j c^n c^j مستقل از متن هست ولی این زبان نه: a^n b^j a^n b^j

این زبانو a^n b^j c^n c^j میشه به این شکل نوشت:
a^n b^j c^j c^n
اگر a اومد که پوش میشه، b اومد پوش میشه تو استک، اگه c اومد تا موقعی که b تو استک میبینه، pop میکنیم،اگر b‌ها تموم شد و بازم c میومد، تا موقعی که استک a داره pop میکنیم. اگرc تموم شد و بازم تو استک a داشتیم که reject میشه.و همینطور حالات دیگه ای هم میشه واسه عدم پذیرش رشته در نظر گرفت.

اما تو زبان دوم نیاز به دو حافظه داریم.

البته قسمت دومش رو من یه اصلاح کنم
۲-- اگر تعداد b‌ها بیشتز از a بود به ازای هر b یک a پاپ می کنیم بعد از پاپ همه a‌ها بقیه b‌ها پوش می شود و
سپس به ازای هر C یک b از پشته pop می کنیم وقتی تعداد b‌ها تموم شد، C های باقیمانده رو push می کنیم.
در پایان به ازای هر d یک C را Pop می کنیم .
با تمام شدن رشته ،پشته هم خالی می شود و رشته پذیرفته می شه.

در مورد گزینه چهار هم که گفته:
مکمل هر زبان مستقل از متن یک زبان بازگشتی است ولی مستقل از متن نیست .

قسمت اول جمله درسته ولی وقتی می گه مستقل از متن نیست درست نیست
چون زبان های مستقل از متن تحت عمل مکمل بسته نیست ولی وجود داره زبانی که مستقل از متن باشه و مکملش هم مستقل از متن باشد .