سلام.
چرا زبان زیر مستقل از متنه؟
a^n b^m c^k: n<= m+k <= 3n
(۰۳ دى ۱۳۹۰ ۱۲:۵۸ ق.ظ)sh_aa نوشته شده توسط: سلام.
چرا زبان زیر مستقل از متنه؟
a^n b^m c^k: n<= m+k <= 3n
ببینید
من فکر کنم چون برای طراحی چنین زبانی نمیشه DFA , NFA رسم کرد و میشه ماشین PDA , TM رو رسم کرد پس این زبان مستقل از متنه.
به عبارتی برای طراحی ماشین این زبان نیاز به حافظه داریم. فقطم PDA به بالا میتونن این قابلیت رو داشته باشند.
ماشینی که این زبان رو قبئل می کنه به این صورت کار میکنه که هر a تعداد ۳تا علامت تو پشته می زاره و هر b یا c تعذاد ۱ یا ۲ یا ۳ تا از علامت‌ها رو از پشته بر میداره