تالار گفتمان مانشت
۲ نکته ساده و طلایی نظریه - نسخه‌ی قابل چاپ

۲ نکته ساده و طلایی نظریه - milad_iq - 18 مهر ۱۳۹۰ ۱۱:۴۳ ب.ظ

سلام
۲ تا نکته بسیار ساده
اما بی نهایت کاربردی.... این نکات به وضوح در کتاب لینز ندیدم.شاید در مفهوم نهفته باشه....
۱/
زبان منظم ذاتا مبهم نیست اما میتوان برای آن گرامر منظم مبهم ارائه کرد
۲/
گرامر سادهS.G مبهم نیست.پس میتونه یکی از ملاک های تشخیص غیر مبهم بودن زبان این باشه که تشخیص بدیم گرامر ساده است...گرامر ساده قوانین سهل الوصولی داره..به کتاب لینز مراجعه شود.

۲ نکته ساده و طلایی نظریه - hadi_m - 02 آذر ۱۳۹۰ ۱۰:۲۸ ب.ظ

هر دو این نکته‌ها در کتاب لینز ذکر شده البته به عنوان تمرین عنوان شده
تمرین شش فصل ۵
و تمرین ۴

یه نکته در تکمیل توضیح دوستمون جهت تشخیص ابهام:
اصولا ابهام از انجا ناشی میشود که ماشین سر چند راهی گیر میکند و باید از میان مسیرهای موجود گزینش کند تا ببیند میتواند برای گرامر مربوطه یک درخت اشتقاق تولید کند یا خیرر
از انجا که در زبان منظم nfa و dfa معادل هستنند و میتوان به هم تبدیل کرد و چون dfa فاقد ابهام هست لذا زبان منظم به هیچ وجه نمیتواند مبهم باشد.

نکته بعدی اینکه تنها nfa و dfa معادل هم میباشند و این حکم برای ماشین پشته ایی معین و نامعین به هیچ عنوان صدق نمیکنه و همچنین در ماشین تورینگ.
اصولا اثبات اینکه یک زبان ذاتا مبهم نیست کار چندان ساده ایی نیست اما با توجه به یک سری نکات میتوان با استدلالهی ذهنی به نتایج مناسبی رسید.