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

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

ارسال:
  

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 برسیم با پشته کاری نداریم. الان توی پشتمون یه تعداد ۱ و یه ۰ هست که جمعشون برابر شماره حرف موردنظرمونه. به تعداد ۱ها کاراکترهارو پوش میکنیم و کاریشون نداریم و بعد کاراکتری که همراه با پاپ شدن ۰ میخونیم رو با حرف مذکور مقایسه میکنیم. اگه یکی نبودن به حالت پایانی میریم. چون ماشینش نامعینه به ازای همه کاراکترهای رشته اول این مقایسه رو انجام میده. مقایسه طول رو هم به همین روش انجام میده.
نمیدونم چرا استادمون اثباتشو یهو سر پایانترم ازما خواست.



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  کدام زبان برای هوش مصنوعی بهتر است؟ فرق بین زبان های هوش مصنوعی چیست؟ azam2075 ۳ ۵,۴۳۴ ۱۴ مهر ۱۴۰۰ ۰۷:۲۱ ب.ظ
آخرین ارسال: علیصا
  تشخیص گوگل مپس با Live View AR برای مکان دقیق elecomco ۱ ۳,۸۲۰ ۰۵ بهمن ۱۳۹۹ ۰۲:۴۹ ب.ظ
آخرین ارسال: kooshaideal1
  گرامر منظم Sanazzz ۶ ۶,۱۲۰ ۳۱ اردیبهشت ۱۳۹۸ ۰۴:۳۲ ب.ظ
آخرین ارسال: Sanazzz
  تشخیص خطا در تحلیلگر لغوی یا نحوی zahra2012 ۵ ۷,۶۸۶ ۲۶ مرداد ۱۳۹۷ ۰۴:۲۹ ب.ظ
آخرین ارسال: tohid.salmani
  تشخیص کاراکتر با شبکه عصبی safoora s ۴ ۳,۶۸۵ ۱۸ مرداد ۱۳۹۷ ۱۰:۵۰ ب.ظ
آخرین ارسال: kilookiloo
Photo ساده سازی عبارت منظم etedadi ۰ ۱,۷۸۶ ۱۶ خرداد ۱۳۹۷ ۰۷:۰۴ ب.ظ
آخرین ارسال: etedadi
  تشخیص دو قضیه از هم Mr.R3ZA ۵ ۴,۹۰۱ ۳۱ اردیبهشت ۱۳۹۷ ۱۲:۱۴ ق.ظ
آخرین ارسال: pioneer01
  تشخیص گروه در شبکه های اجتماعی osho ۴۸ ۳۱,۰۰۱ ۲۸ فروردین ۱۳۹۷ ۰۷:۵۲ ب.ظ
آخرین ارسال: atahmasebi
Exclamation تشخیص نوع زبان و گرامر به صورت تستی و سریع kamran_maneshtir ۰ ۲,۰۴۰ ۰۲ بهمن ۱۳۹۶ ۰۷:۴۶ ب.ظ
آخرین ارسال: kamran_maneshtir
  تشخیص توالی پذیر نمایی (VSS) jumper ۰ ۱,۴۱۱ ۲۴ دى ۱۳۹۶ ۱۰:۱۹ ق.ظ
آخرین ارسال: jumper

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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