(۰۸ بهمن ۱۳۹۳ ۰۷:۴۶ ب.ظ)arefeh.hp نوشته شده توسط:  سلام



چه روشی وجود داره که بفهمیم یک زبان از نوع خطی هست؟!

سلام
یکی از راه های تشخیص زبان خطی اینه که بتونیم اون زبانو به وسیله یک ماشین پشته ای single turn پیاده سازی کنیم.حالا ماشین پشته ای single turn یعنی اگه یکبار پشته شروع به کم کردن ارتفاع کرد(برداشتن نمادها از پشته) دیگه دوباره اونو افزایش نده.(گذاشتن نمادها در پشته)
مثلا زبان (a^n b^n )
با دیدن a،aها رو تو پشته پوش میکنیم و وقتی b اومد شروع می کنیم به پاپ کردن.الان شروع کردیم به کاهش ارتفاع پشته و دیگه هرگز ارتفاع پشته رو زیاد نکردیم.پس این زبان خطیه.
موفق باشید