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

سلام
این سوال را خود سنجش گزینه ۴ زده
پوران گفته فقط واسه سه تای اولی میشه با دو حالت کشید ، پس گزینه ۳
پارسه گفته گزینه ۴ البته تناقض در مطالب پارسه وجود داره
۱/ پارسه در متن درسش گفته برای هر NPDA یک NPDA با حداکثر ۳ وضعیت وجود دارد که میتوان آن را به دو وضعیت هم کاهش داد
۲/ و در جواب این سوال گفته برای هر زبان مستقل از متن یک PDA با حداکثر دو حالت وجود دارد



حالا سوال اینجاست که
۱/ آیا برای هر PDA یک PDA با دو حالت هست یا خیر؟ یا این قانون فقط در مورد NPDA هست.
۲/ یا اصلا چنین قانونی وجود نداره و باید بشینیم واسه زبانهای گفته شده PDA بکشیم؟

سلام. یه قاعده داریم که با کمک گرامر مستقل از متن میتونیم یه ماشین پشته ای 3حالته پیاده سازی کنیم. وجود 3 حالت هم برای فهم بهتره مسئلست؛ وگرنه میشه با 2حالت هم پیاده سازیش کرد. البته ناگفته نمونه که یه تفاوت هایی هم با ماشینی که معمولاً استفاده میشه داره. مثلاً در یه حرکت 4 تا پوش و 3 تا پاپ میتونه داشته باشه که اگه قراره به حالت عادی (فقط یه پاپ در هر مرحله) تعداد حالات از 2 و 3 خیلی بیشتر میشه.
4 تا زبان نوشته شده هم همشون منظم هستن. بدون درنظر گرفتن اون قاعده هم میشه برای همشون ماشین پشته ای دو حالته طراحی کرد. یه حالتش پایانی و یه حالتش غیر پایانی. البته برای زبان 1 و 2 هم با توجه به الفبا میشه ماشین 1 حالته هم طراحی کرد.

(07 آذر 1392 01:19 ب.ظ)Jooybari نوشته شده توسط: [ -> ]سلام. یه قاعده داریم که با کمک گرامر مستقل از متن میتونیم یه ماشین پشته ای ۳حالته پیاده سازی کنیم. وجود ۳ حالت هم برای فهم بهتره مسئلست؛ وگرنه میشه با ۲حالت هم پیاده سازیش کرد. البته ناگفته نمونه که یه تفاوت هایی هم با ماشینی که معمولاً استفاده میشه داره. مثلاً در یه حرکت ۴ تا پوش و ۳ تا پاپ میتونه داشته باشه که اگه قراره به حالت عادی (فقط یه پاپ در هر مرحله) تعداد حالات از ۲ و ۳ خیلی بیشتر میشه.
۴ تا زبان نوشته شده هم همشون منظم هستن. بدون درنظر گرفتن اون قاعده هم میشه برای همشون ماشین پشته ای دو حالته طراحی کرد. یه حالتش پایانی و یه حالتش غیر پایانی. البته برای زبان ۱ و ۲ هم با توجه به الفبا میشه ماشین ۱ حالته هم طراحی کرد.

ممنون اقای جویباری .
البته من خیلی گیر ماشین پشته ای کشیدن برای این زبانها نبودم و فقط این قاعده اذیتم میکرد که طبق عادت بی اعتمادی من به کتاب همیشه غلط پارسه و پوران ، خواستم شکم را برطرف کنم. که خب این بار انگار پارسه درست گفته بود.