(۱۹ آذر ۱۳۹۰ ۱۰:۲۴ ق.ظ)Mojtaba نوشته شده توسط:  l2 حتی یک زبان مستقل از متن هم نیست.

تصحیح شد

n

(19 آذر ۱۳۹۰ ۱۰:۲۴ ق.ظ)Mojtaba نوشته شده توسط:  سلام دوست خوب من.
ای ول خوشم میاد توی نظریه سنگ تموم گذاشتی(کاری که من میخواستم توی ماه اخر انجام بدم را شما زودتر شروع کردی).
ان شالله که همیشه موفق و پیروز باشی.
والا آن چیزی که به نظر من میرسه‌، اینکه گزینه ۳ صحیحه.

l1 منظمه چرا که اگه w, ریورس w را اپسیلون بگیریم با v قادر به تولید زبان * {a,b} هستیم.
l2 هم یک زبان مستق از متنه به نظر من.
l3 هم یک زبان منظم هستش (به نظر من اگر dfa زبان l5 را بدست بیاریم بعد ریورسش کنیم (باز هم منظمه) بعد با زبان منظم l4 اشتراکشون را بگیریم که بازم منظمه پس زبان l3 هم منظم میشه)
لطفا دوستان نظراتشون را بگن!

قلب‌ها جز با یاد

سلام
خیلی ممنون که وقتتون رو میزارید و پاسخ میدین
به نظر من هم گزینه ۳ درسته
اما کتاب من گزینه ۴ رو زده گفتم شاید من مثل سوالات قبلی که گذاشته بودم من اشتباه می کنم برای همین هم اینجاگذاشتم مثل اینکه این دفعه نحوه‌ی نگاه کردن من به مسئله (از پایین به بالا )درست بوده و کتاب گزینه اشتباه رو انتخاب کرده
چرا که زبان L1 دیگه واقعا منظمه چون V متعلق به*^( a+b) پس رابطه‌ی بین W , معکوس W از بین میره

گزینه‌ی ۳ صحیحه . زبان دو به نظرم مستقل از متنه . در تصحیح حرف دوستمون که گفتن مستقل از متن نیست .

(۱۵ دى ۱۳۹۰ ۰۱:۳۵ ب.ظ)Bache Mosbat نوشته شده توسط:  گزینه‌ی ۳ صحیحه . زبان دو به نظرم مستقل از متنه . در تصحیح حرف دوستمون که گفتن مستقل از متن نیست .

با سلام:
L1‌، منظم نیست ها...
چطوری می شه با DFA تشخیص داد‌، رشته‌ی w رو خونده بعد معکوس همون را بخونه...
این استک می خواد
من که با گ۱ موافقم

یه سوال دیگه.ایا بدون بلد بودن لم تزریق میشه تمام سولات مرتبط به زبانها رو حل کرد؟راه ساده تری وجود داره برای تشخیص؟

بله می شه! با تمرین حل کردن زیاد!

من با این سوال مشکل دارم. جواب های بالا خیلی متناقض و طبق چیزی که سنجش میگه گزینه ۴ جوابه.
زبان L1 چطور می تونه منظم باشه؟ مگه W و W Reverse می تونن بدون پشته تشخیص داده بشن؟
دلیلی هم که در بالا برای منظم بودنش میگید رو متوجه نمیشم، یعنی چی که W رو لاندا فرض می کنید. W می تونه هر رشته ای از a و b باشه و بعد از اون باید دقیقا برعکس اون رشته هم وجود داشته باشه و بعدش دیگه مهم نیست. که این‌ها همه با پشته باید تشخیص داده بشه.
L2 هم به نظرم مستقل از متن نیست. اما میشه یکی کامل‌تر توضیح بده که چطور قابل تشخیص؟

(۲۲ دى ۱۳۹۰ ۱۲:۳۸ ق.ظ)shervinrs نوشته شده توسط:  من با این سوال مشکل دارم. جواب های بالا خیلی متناقض و طبق چیزی که سنجش میگه گزینه ۴ جوابه.
زبان L1 چطور می تونه منظم باشه؟ مگه W و W Reverse می تونن بدون پشته تشخیص داده بشن؟
دلیلی هم که در بالا برای منظم بودنش میگید رو متوجه نمیشم، یعنی چی که W رو لاندا فرض می کنید. W می تونه هر رشته ای از a و b باشه و بعد از اون باید دقیقا برعکس اون رشته هم وجود داشته باشه و بعدش دیگه مهم نیست. که این‌ها همه با پشته باید تشخیص داده بشه.
L2 هم به نظرم مستقل از متن نیست. اما میشه یکی کامل‌تر توضیح بده که چطور قابل تشخیص؟

در مورد L1:
هر رشته ای که وارد می شه شامل حروفی از a و b است.خوب تمامی اینها رو اصلا به V نسبت می دیم. چون هیچ محدودیتی ندارمو فرض می کنیم اصلا W ای وجود ندارد که به خواد معکوسش هم باشه.
دقت کنید چون الفبای ما *{b,a} است می تونیم کلا w رو نادید بگیریم. ولی اگه + بود به این راحتی قابل استدلال نیست. چون حتما باید یک الفبایی مربوط به W باشه.
همین صورت یک با + جز تمرینات لینز است که گفته نامنظمه.

در مورد L2:
واقعا مستقل از متن نیست. پس مشکلی نیست

دوستان سنجش گزینه ۴ رو انتخاب کرده
در مورد L1 به نظرم منظمه ولی خب این چیزی که شما هم میگید قابل انکار نیست.
ولی فقط همین فرضتون میتونه درست باشه.

(۲۲ دى ۱۳۹۰ ۰۱:۲۹ ق.ظ)پشتکار نوشته شده توسط:  دوستان سنجش گزینه ۴ رو انتخاب کرده
در مورد L1 به نظرم منظمه ولی خب این چیزی که شما هم میگید قابل انکار نیست.
ولی فقط همین فرضتون میتونه درست باشه.

تجربه نشون داده سنجش هم آدمه و اشتباه می کنه!

من به نظرم گزینه ۴ درسته...! (دعوام نکنیدا )

خب زبان سوم که معلومه دیگه منظمه (چون زبان های منظم تحت عمل معکوس بسته اند وقتی خودش و معکوسش منظم باشند قطعاً خودش هم منظمه......!
زبان یک چون میدونیم w و W^r مستقل از متنه .... حاصل الحاقش با یک زبان منظم (V) حتماً منظم نیست....!
زبان دو هم با یک ماشین تورینگ قابل پیاده سازیه و من فکر میکنم حساس به متن باشه...!

سلام. مثل اینکه L2 مستقل از متنه. میشه یه ماشین پشته ای نامعین براش ساخت.
ساخت ماشینش یکم دردسر داره.
یه بار بدون درنظر گرفتن رشته فقط طولشو چک میکنیم. (چون نامعینه یه حالت جدا درنظر میگیریم.)
به ازای اولین حرف توی پشته یه ۰ پوش میکنیم. بعد ۲ حالت رو برای یه حرف درنظر میگیریم که با هرکدوم از کاراکترهای a,b به یه حالت بره. با گرفتن بقیه حروف تا به c برسیم با پشته کاری نداریم. الان توی پشتمون یه تعداد ۱ و یه ۰ هست که جمعشون برابر شماره حرف موردنظرمونه. به تعداد ۱ها کاراکترهارو پوش میکنیم و کاریشون نداریم و بعد کاراکتری که همراه با پاپ شدن ۰ میخونیم رو با حرف مذکور مقایسه میکنیم. اگه یکی نبودن به حالت پایانی میریم. چون ماشینش نامعینه به ازای همه کاراکترهای رشته اول این مقایسه رو انجام میده. مقایسه طول رو هم به همین روش انجام میده.
نمیدونم چرا استادمون اثباتشو یهو سر پایانترم ازما خواست.