صفحه‌ها: ۱ ۲
فرض کنید W^R معکوس رشته W و L4,L5 دو زبان منظم دلخواه باشند . زبان های L1,L2,L3 به شرح زیر است
[tex]L_{1}=\left \{ WW^{R}V|V,W\epsilon \left \{ a,b \right \}^{*} \right \}[/tex]
[tex]L_{2}=\left \{ W_{1}cW_{2}|W_{2},W_{1}\epsilon \left \{ a,b \right \}^{*} ,W_{1}\neq W_{2}\right \}[/tex]
[tex]L_{3}=\left \{ W|W\epsilon L_{4} ,W^{R}\epsilon L_{5}\right \}[/tex]
کدام گزینه درست است؟
۱ )L1,L2,L3 نامنظم اند.
۲ )L1,L2,L3 هرسه منظم اند.
۳ )L1,L3 منظم ولی L2 نامنظم است .
۴) L2,L1 نامنظم اند اما L3 منظم است.
ممنون از همه دوستان که کمک می کنید.
سلام دوست خوب من.
ای ول خوشم میاد توی نظریه سنگ تموم گذاشتی(کاری که من میخواستم توی ماه اخر انجام بدم را شما زودتر شروع کردی).
ان شالله که همیشه موفق و پیروز باشی.
والا آن چیزی که به نظر من میرسه، اینکه گزینه ۳ صحیحه.
l1 منظمه چرا که اگه w, ریورس w را اپسیلون بگیریم با v قادر به تولید زبان * {a,b} هستیم.
l2 حتی یک زبان مستقل از متن هم نیست.
l3 هم یک زبان منظم هستش (به نظر من اگر dfa زبان l5 را بدست بیاریم بعد ریورسش کنیم (باز هم منظمه) بعد با زبان منظم l4 اشتراکشون را بگیریم که بازم منظمه پس زبان l3 هم منظم میشه)
لطفا دوستان نظراتشون را بگن!
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 برابر لاندا باشه . ازونجا که V عضو سیگما استار هست پس کل زبان‌ها‌ی دیگه رو پوشش می ده. پس این زبان برابر سیگما استاره .
یه سوال دیگه.ایا بدون بلد بودن لم تزریق میشه تمام سولات مرتبط به زبانها رو حل کرد؟راه ساده تری وجود داره برای تشخیص؟
بله می شه! با تمرین حل کردن زیاد!
(۱۹ آذر ۱۳۹۰ ۱۰:۲۴ ق.ظ)Mojtaba نوشته شده توسط: l2 حتی یک زبان مستقل از متن هم نیست.
تصحیح شد
(۱۹ دى ۱۳۹۰ ۰۵:۳۵ ب.ظ)hadi_m نوشته شده توسط:(19 آذر ۱۳۹۰ ۱۰:۲۴ ق.ظ)Mojtaba نوشته شده توسط: l2 حتی یک زبان مستقل از متن هم نیست.باسلاام
زبان L2 مستقل از متن هستش و به راحتی میشه براش گرامر نوشت و حتی با ماشین پشته به راحتی قابل تشخیص هستش . دقت کنید چون W1 و W2 فاقد کاراکتر c میباشند بنابراین مرز بین دورشته قابل تشخیص به بوده و میتوان این دو رشته را از لحاظ طول با هم مقایسه کرد.
ناگفته پیداست که حتی اگر این دور رشته حاوی کارکتر c هم میبودنند باز هم مستقل از متن بودنند اما از نوع غیر قطعی چون با قاطعیت نمیتونا مرز بین دو رشته را تشخیص داد.
با تشکر
زبان ۲ مستقل از متن نیست ها! با پشته نمی شه این کنترل رو انجام داد.
وقتی مثلا aaabbcaaabb رشته ورودی باشد در پشته قسمت اول اینجوریه:
b
b
a
a
a
به c که می رسیم می ندازیمش دور بعد a میاد.
حالا a رو چطوری با a پایین پشته می خواین مقایسه کنید؟
من با این سوال مشکل دارم. جواب های بالا خیلی متناقض و طبق چیزی که سنجش میگه گزینه ۴ جوابه.
زبان 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:
واقعا مستقل از متن نیست. پس مشکلی نیست
اگه w رو نال فرض کنیم رشتمون میشه v که همون سیکما استاره (تمام رشته های الفبا رو قبول میکنه). سیکما استار هم منظمه.
برای L2 نیاز به پشته داریم. مثال آقای صفایی نشون میده که بدون پشته نمیشه رشته های زبانو تولید کرد. این زبان مستقا از متن نامعینه.
دوستان سنجش گزینه ۴ رو انتخاب کرده
در مورد L1 به نظرم منظمه ولی خب این چیزی که شما هم میگید قابل انکار نیست.
ولی فقط همین فرضتون میتونه درست باشه.
(۲۲ دى ۱۳۹۰ ۰۱:۲۹ ق.ظ)پشتکار نوشته شده توسط: دوستان سنجش گزینه ۴ رو انتخاب کرده
در مورد L1 به نظرم منظمه ولی خب این چیزی که شما هم میگید قابل انکار نیست.
ولی فقط همین فرضتون میتونه درست باشه.
تجربه نشون داده سنجش هم آدمه و اشتباه می کنه!
