تالار گفتمان مانشت

سلام دوستان


زبان {a^n b^m c^n d^m |n,m>=0} مستقل از متن هست یا وابسته به متن؟

توی کتاب من زده که هم این زبان و هم متممش بازگشتی هستن... درسته؟

ممنونم

سلام. حساس به متنه. اول باید تعداد aها رو ذخیره کنید. بعد تعداد b ها باید دخیره بشه. بعدش باید تعداد cها با aها مقایسه بشه. برای رسیدن به aها باید bهارو دور بریزیم. نمیشه با پشته پیاده سازیش کرد.

سلام
به دلیل ساختار lifo ی پشته امکان پیاده سازی آن با pda وجود ندارد اما حساس به متن است زیرا در ماشین تورینگ مربوط به آن کافیست از |w| خانه از حافظه استفاده کنیم. و بازگشتی است چون هم عضویت رشته در زبان را می توانیم تصمیم بگیریم و هم عدم عضویت را. علاوه بر این می دانیم همه ی زبان های حساس به متن بازگشتی هستند.