با سلام به دوستان
من یک سوالی برام پیش امده اونم اینه که اقای شاپوری برای زبان L2 مثلا گفتا اگر w رو مساوی لاندا بگیریم زبان میشه منظم خب سوال برای من اینا که اگ نگیریم چی اونقت نیاز به حافظه کمکی برای تشخیص وارون رشته هس دگ و پس زبان نامنظم میشه
پس چرا میگن منظمه لطفا یه توضیح بدین من از ابهام در بیام با تشکر
![[تصویر: 421021_5u1g_20160907_155137.jpg]](https://img.manesht.ir/421021_5u1g_20160907_155137.jpg)
سلام.
اولا این مسئله توی خیلی از سوالا وجود داره که برای اثبات منظم بودن یک زبان باید متغیر رو لامبدا گرفت وقتی یه متغیر و معکوسش کنار هم هست( این مسئله عمومیت نداره لزوماََ)
خب زبانی که معرفی شده رو اگه بتونیم براش یه DFA یا NFA بکشیم میشه منظم.
الان مشکل اینه که یه رشته و معکوسش باید توی جملات باشه، اما طبق تعریف تمام این متغیر ها میتونن لامبدا باشن. حالا اگه w و reverse ش رو برابر لامبدا بگیریم، بازم همون زبانه، چون میشه u که بازم تعریف همون زبان L2هست، منتهی از شر نگه داری رشته و معکوسش خلاص شدیم. الان میتونیم یه state داشته باشیم که final هست و با a و b به خودش میره یعنی یه ماشین قطعی متناهی داریم و زبان منظم هست.
الان شاید سوال این باشه که پس با این تعریف، اون رشته هایی که آخرشون wو بعد w reverse هست حذف شدند از زبان. خیر الان u همون رشته ها رو هم می سازه و باز میتونه رشته هایی بسازه که انتهای رشته یه زیررشته ای اومده و بعد reverseش. L2 مجموعه ی مرجع هست.
سلام. وقت بخیر.
قبول دارید اگه w رو برابر لاندا بگیریم و در معادله قرار بدیم به زیرمجموعه‌ای از این رشته‌ها میرسیم؟ حالا این زیرمجموعه رو محاسبه میکنیم و میبینیم این زیرمجموعه برابر با مجموعه مرجع یعنی سیکمااستار شده. با توجه به اینکه زیرمجموعه‌ای از رشته‌های یک زبان برابر مجموعه مرجع شده پس اون زبان با مجموعه مرجع برابره. اینکه از کجا متوجه بشیم که باید لاندا رو برای w درنظر بگیریم یه بحث دیگست که فقط باید با حل مثالها به این نتیجه برسید.