تشخیص زبانهای ذاتاً مبهم - نسخه‌ی قابل چاپ

تشخیص زبانهای ذاتاً مبهم - alirezafchh - 22 بهمن ۱۳۹۴ ۱۱:۳۱ ق.ظ سلام دوستان می خواستم بدونم راه تشخیص یک زبان ذاتاً مبهم چیست؟ با تشکر

RE: تشخیص زبانهای ذاتاً مبهم - mahmood19227 - 22 بهمن ۱۳۹۴ ۰۵:۰۷ ب.ظ نه. مورد به مورد باید اثبات بشن. کلا تعدادشون خیلی کمه. تو یک مقاله خوندم که نوشته بود حدود ۵۳ مثال توسط افراد مختلف تو کتابها و مقالات مختلف نوشته شده Sent from my HTC One_E8 dual sim using Tapatalk

RE: تشخیص زبانهای ذاتاً مبهم - Pure Liveliness - 07 خرداد ۱۳۹۵ ۰۸:۱۰ ب.ظ سلام. زبان ها کلا دو دسته هستن: یا ذاتاََ مبهم هستن، یا غیر مبهم. چیزی به اسم زبان مبهم نداریم. اگه حداقل یه گرامر غیر مبهم واسه زبانی وجود داشته باشه بهش میگیم زبان غیر مبهم. زبانی غیر مبهم هست که بشه یه گرامر یا ماشین قطعی براش نوشت. و اگه حداقل بشه یکی واسش نوشت پس میشه بی نهایت تا نوشت. زبانی ذاتاََ مبهم هست که حتی یه گرامر غیر مبهم نداره. زبانی که مستقل از متن هست اگه همه ی گرامر هاش مبهم باشه یعنی برای تمامی گرامر هاش حداقل یه رشته وجود داشته باشه که دو تا درخت اشتقاق یا دو تا LMD یا RMD داشته باشه، اونوقت ذاتا مبهم هست اون زبان.(هیچ گرامر غیر مبهمی نداشته باشه) ــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ​ــــــــــ مثلا زبان مستقل از متن زیر ذاتاََ مبهم هست: {a^n b^n c^m | n,m>=0} اجتماعش با {a^n b^m c^m | n,m>=0} = زبان L S-> S1 | S2 S1 -> AC A -> aAb | lambda C -> cC | lambda S2 -> BD A -> bB | lambda C -> BdC | lambda رشته یa^n b^n c^n رو در نظر بگیرید. هم از S1 ساخته میشه هم از طریق S2 خب پس حداقل یه رشته پیدا کردیم که از دو طریق ساخته بشه توی گرامر این زبان، پس این گرامر مبهم هست. از طرفی این زبان هیچ گرامر غیر مبهمی نداره، در نتیجه میشه زبان ذاتاََ مبهم. البته میشه رفع ابهام کرد از این زبان، میشه توی L1 یا L2 که L اجتماع این دو هست، توی یکیشون m برابر با n نباشه. اونوقته که فقط این رشته از طریق S1 ساخته میشه یا S2 و نه از دو راه. اگه این تغییر اعمال بشه، زبان میشه غیر مبهم. ــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ​ــــــــــ در مجموع یه زبان ذاتاََ مبهم هست که همه ی گرامر هاش مبهم باشن. گرامری هم مبهم هست که حداقل یه رشته تووش دو تا درخت اشتقاق داشته باشه. این یه مثال خوب هست: مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید. مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید. برای درک مفاهیم نظریه و کلاََ، وویس دکتر کارگهی که توی مانشت قرار داره بسیار کمک کننده هست: مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.