چرا زبان {u v w | u = w^R } منظمه؟ حل شد - نسخه‌ی قابل چاپ

چرا زبان {u v w | u = w^R } منظمه؟ حل شد - zimenswall - 21 شهریور ۱۳۹۲ ۰۸:۱۳ ب.ظ من تو این پست خواستم این چندتا زبان رو کنار هم بذارم که تفاوتها و شباهت هاش مشخص باشه که مدیران لطف کردن و بستنش چون قانون انجمن اینه که هر سوالی جدا پرسیده بشه مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید. در ضمن من توی انجمن جستجو کردم بیشتر اینها رو ندیدم و اگر هم پرسیده شده باشه معمولا جواب های کلیشه ای بهش داده شده که ۱/ چون dfa و nfa میشه براش کشید منظمه ۲/ چون نمیتونیم لم تزریق براش بیاریم منظمه ۳/ چون با عبارت منظم میشه نوشتش پس منظمه ۴/ چون نمیتونیم بگیم نامنظمه پس منظمه هدف من تحلیل کلی و تستی واسه اینجور مسائل بود. و چون شکل زبانها باهم مرتبط بود بهتر بود در کنار هم بررسی بشه که بهتر فهمیده بشه. اما من روم مثل سنگ پای قزوینه سوالا رو جدا جدا پرسیدم ۱. زبان [tex]\left \{ u v w: u,v,w \in \sum^{*}, u = w^{R\R} \right \}[/tex] تحلیل من: اگر وسط رشته را توجه کنیم میبینیم که v یک رشته شامل سیگما استار (دیگه نمیگم سیگما) هست که وقتی در کنار رشته w و u قرار میگیره باعث میشه ارتباط بین این دو رشته از بین بره. یعنی به عبارتی vباعث میشه که u و w اول و آخر زبان رو در خودش قاطی کنه و زبان سیگما استار رو بسازه. تحلیل azk84 درسته تقریباً، ولی اگه کمی دقیق‌تر بخوایم موضوع رو تحلیل کنیم: موضوع از بین رفتن ارتباط بین u و w نیست. یکی از حالت‌های خاص رشته‌های این زبان وقتی هستش که u و w برابر e (اپسیلون) باشند. در این حالت رشته‌ی باقیمانده برابر v خواهد بود که به تنهایی کل سیگما استار رو می‌سازه. دیگه همه‌ی حالت‌های دیگه برای u و w هر چی که باشه چیزی نمیتونه به این مجموعه‌ی سیگما استار اضافه کنه (چون همه چیز توی خود سیگما استار هست به هر حال) و در نتیجه زبان ما میشه سیگما استار که منظمه.