زمان کنونی: ۲۳ آذر ۱۳۹۷, ۰۹:۳۲ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

سال ۸۱ تشخیص زبان منظم

ارسال:
  

ahmadnouri پرسیده:

سال ۸۱ تشخیص زبان منظم

فرض کنید 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 منظم است.


ممنون از همه دوستان که کمک می کنید.

۲
ارسال:
  

Mojtaba پاسخ داده:

تشخیص زبان منظم تست سال ۸۱

سلام دوست خوب من.
ای ول خوشم میاد توی نظریه سنگ تموم گذاشتی(کاری که من میخواستم توی ماه اخر انجام بدم را شما زودتر شروع کردی).
ان شالله که همیشه موفق و پیروز باشی.
والا آن چیزی که به نظر من میرسه‌، اینکه گزینه ۳ صحیحه.

l1 منظمه چرا که اگه w, ریورس w را اپسیلون بگیریم با v قادر به تولید زبان * {a,b} هستیم.
l2 حتی یک زبان مستقل از متن هم نیست.
l3 هم یک زبان منظم هستش (به نظر من اگر dfa زبان l5 را بدست بیاریم بعد ریورسش کنیم (باز هم منظمه) بعد با زبان منظم l4 اشتراکشون را بگیریم که بازم منظمه پس زبان l3 هم منظم میشه)
لطفا دوستان نظراتشون را بگن!
Jooybari، در تاریخ ۲۰ تیر ۱۳۹۱ ۰۲:۰۷ ب.ظ برای این مطلب یک پانوشت گذاشته است:

L2 مستقل از متنه.

ارسال:
  

hadi_m پاسخ داده:

RE: تشخیص زبان منظم تست سال ۸۱

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

تصحیح شد
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

Bache Mosbat پاسخ داده:

تشخیص زبان منظم تست سال ۸۱

قبلا مشابه زبان L1 منظم بودنش توضیح داده شد.
فرض کن W برابر لاندا باشه . ازونجا که V عضو سیگما استار هست پس کل زبان‌ها‌ی دیگه رو پوشش می ده. پس این زبان برابر سیگما استاره .

۰
ارسال:
  

Jooybari پاسخ داده:

تشخیص زبان منظم تست سال ۸۱

اگه w رو نال فرض کنیم رشتمون میشه v که همون سیکما استاره (تمام رشته های الفبا رو قبول میکنه). سیکما استار هم منظمه.
برای L2 نیاز به پشته داریم. مثال آقای صفایی نشون میده که بدون پشته نمیشه رشته های زبانو تولید کرد. این زبان مستقا از متن نامعینه.

۰
ارسال:
  

ahmadnouri پاسخ داده:

تشخیص زبان منظم تست سال ۸۱

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

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

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

۰
ارسال:
  

Bache Mosbat پاسخ داده:

تشخیص زبان منظم تست سال ۸۱

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

ارسال:
  

presidenthamid پاسخ داده:

RE: تشخیص زبان منظم تست سال ۸۱

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

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

۰
ارسال:
  

navid-p پاسخ داده:

تشخیص زبان منظم تست سال ۸۱

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

۰
ارسال: #۱۰
  

Bache Mosbat پاسخ داده:

تشخیص زبان منظم تست سال ۸۱

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

۰
ارسال: #۱۱
  

shervinrs پاسخ داده:

تشخیص زبان منظم تست سال ۸۱

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

ارسال: #۱۲
  

مازیار صفایی پاسخ داده:

RE: تشخیص زبان منظم تست سال ۸۱

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

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

در مورد L2:
واقعا مستقل از متن نیست. پس مشکلی نیستBig Grin
یافتن تمامی ارسال‌های این کاربر

۰
ارسال: #۱۳
  

پشتکار پاسخ داده:

RE: تشخیص زبان منظم تست سال ۸۱

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

ارسال: #۱۴
  

مازیار صفایی پاسخ داده:

RE: تشخیص زبان منظم تست سال ۸۱

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

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

۰
ارسال: #۱۵
  

variant20002000 پاسخ داده:

تشخیص زبان منظم تست سال ۸۱

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

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

۰
ارسال: #۱۶
  

Jooybari پاسخ داده:

تشخیص زبان منظم تست سال ۸۱

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  سال ۹۲ سئوال ۵۶ - تشخیص نوع چند زبان iman_n21 ۱۵ ۳,۸۱۴ ۲۲ بهمن ۱۳۹۲ ۰۶:۱۶ ب.ظ
آخرین ارسال: hosshah
  سال ۸۰سوال۳۸ تشخیص ابهام و قطعیت گرامر fas ۵ ۱,۴۴۱ ۲۲ بهمن ۱۳۹۲ ۱۲:۵۹ ق.ظ
آخرین ارسال: Jooybari
  سال ۸۶ ثابت لم پامپینگ زبان های مستقل از متن - hosshah ۱۱ ۳,۱۴۷ ۱۵ بهمن ۱۳۹۲ ۰۸:۳۶ ب.ظ
آخرین ارسال: zahra2012
  سال ۹۱ سوال ۵۶ جابجایی کاراکترهای زوج و فرد رشته های زبان منظم fas ۱ ۱,۱۶۵ ۱۱ بهمن ۱۳۹۲ ۰۲:۱۳ ب.ظ
آخرین ارسال: Riemann
  سال ۸۷ علوم کامپیوتر تشخیص مستقل از متن- majidfathi69 ۵ ۱,۸۴۸ ۱۰ بهمن ۱۳۹۲ ۰۶:۵۲ ب.ظ
آخرین ارسال: Jooybari
  سوال های کنکور ۸۹، کوچکترین اوتوماتا و تشخیص عبارت درست m-behdad ۱ ۱,۰۰۱ ۰۷ بهمن ۱۳۹۲ ۰۱:۵۰ ق.ظ
آخرین ارسال: Jooybari
  سال ۹۰سوال ۶۱، عضویت رشته به زبان m-behdad ۱ ۹۳۸ ۰۳ بهمن ۱۳۹۲ ۰۲:۴۶ ب.ظ
آخرین ارسال: Jooybari
  سال ۸۶- سوال ۵۶- قطعی بودن زبان مستقل از متن El@he ۱۲ ۳,۵۸۳ ۲۷ دى ۱۳۹۲ ۰۶:۳۴ ب.ظ
آخرین ارسال: ۱-۱
  سال ۸۸ علوم کامپیوتر زبانهای منظم - m@hboobe ۲ ۱,۳۰۹ ۳۱ شهریور ۱۳۹۲ ۱۲:۵۶ ق.ظ
آخرین ارسال: m@hboobe
  سال ۸۴سوال زبان منظم tabassomesayna ۱۳ ۴,۲۷۵ ۱۵ شهریور ۱۳۹۲ ۱۱:۲۰ ب.ظ
آخرین ارسال: tabassomesayna

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close