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

تعیین نوع زبان( مستقل از متن یا منظم) ازمون های آزمایشی

ارسال:
  

AZ_AMIR پرسیده:

تعیین نوع زبان( مستقل از متن یا منظم) ازمون های آزمایشی

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


فایل‌(های) پیوست شده

نقل قول این ارسال در یک پاسخ

۲
ارسال:
  

msour44 پاسخ داده:

RE: تعیین نوع زبان( مستقل از متن یا منظم) ازمون های آزمایشی

سلام
اول منظم بودن [tex]L_2[/tex] را اثبات می کنیم!!!
[tex]L_2=\{a^nb^m\: \mid\: m\ne n\: or\: m\ne2n\}=\{a^{\ast}b^{\ast}\}-\{a^nb^m|\: m=n\: and\: m=2n\}=\{a^{\ast}b^{\ast}\}-\{\lambda\}[/tex]
باید توجه کرد که چون محدوده مقادیر برای n ,m داده نشده انها را [tex]n,m\ge0[/tex] میگیرم همچنین شرط [tex]m\ne n\: or\: m\ne2n[/tex] مکملش برابر با [tex]m=n\: and\: m=2n[/tex] که فقط رشته تهی در این شرط صدق می کند توجه شود که زبان مرجع ما در اینجا [tex]a^{\ast}b^{\ast}[/tex] است پس [tex]L_2[/tex] منظم است پس گزینه ۲ رد می شود ولی گزینه ۴ را نمی توان رد کرد چون اگر زبانی منظم باشد مستقل از متن هم هست پس می توانیم بگیم که زبان دوم مستقل از متن هم می باشد.
برای اثبات مستقل از متن بودن [tex]L_1[/tex] : اگر فرض کنیم منظم است (در نتیجه مستقل از متن هم می شود) چون زبان دوم منظم است پس گزینه ۱ درست و گزینه ۳ هم درست(منظم بودن باعث مستقل از متن بودن هم ) می شود.پس اگر فرض کنیم تست درست تعریف شده باشد(عمرا) پس زبان اول منظم نیست.برای اثبات مستقل از متن بودن دارم:
[tex]L_1=\{a^nb^m|m\ne n\: and\: m\ne2n\}=\{a^{\ast}b^{\ast}\}-\{a^nb^m|m=n\: or\: m=2n\}=\{a^nb^m|\: n>m\: or\: n<m\: or\: m>2n\: or\: m<2n\}[/tex]
در واقع اجتماع ۴ زبان مستقل از متن است و طبق بسته بودن زبان های مستقل از متن تحت اجتماع پس زبان اول مستقل از متن می باشد رد گزینه ۴ و جواب گزینه ۳
نقل قول این ارسال در یک پاسخ

ارسال:
  

AZ_AMIR پاسخ داده:

RE: تعیین نوع زبان( مستقل از متن یا منظم) ازمون های آزمایشی

(۰۲ اردیبهشت ۱۳۹۶ ۰۹:۰۰ ب.ظ)msour44 نوشته شده توسط:  سلام
اول منظم بودن [tex]L_2[/tex] را اثبات می کنیم!!!
[tex]L_2=\{a^nb^m\: \mid\: m\ne n\: or\: m\ne2n\}=\{a^{\ast}b^{\ast}\}-\{a^nb^m|\: m=n\: and\: m=2n\}=\{a^{\ast}b^{\ast}\}-\{\lambda\}[/tex]
باید توجه کرد که چون محدوده مقادیر برای n ,m داده نشده انها را [tex]n,m\ge0[/tex] میگیرم همچنین شرط [tex]m\ne n\: or\: m\ne2n[/tex] مکملش برابر با [tex]m=n\: and\: m=2n[/tex] که فقط رشته تهی در این شرط صدق می کند توجه شود که زبان مرجع ما در اینجا [tex]a^{\ast}b^{\ast}[/tex] است پس [tex]L_2[/tex] منظم است پس گزینه ۲ رد می شود ولی گزینه ۴ را نمی توان رد کرد چون اگر زبانی منظم باشد مستقل از متن هم هست پس می توانیم بگیم که زبان دوم مستقل از متن هم می باشد.
برای اثبات مستقل از متن بودن [tex]L_1[/tex] : اگر فرض کنیم منظم است (در نتیجه مستقل از متن هم می شود) چون زبان دوم منظم است پس گزینه ۱ درست و گزینه ۳ هم درست(منظم بودن باعث مستقل از متن بودن هم ) می شود.پس اگر فرض کنیم تست درست تعریف شده باشد(عمرا) پس زبان اول منظم نیست.برای اثبات مستقل از متن بودن دارم:
[tex]L_1=\{a^nb^m|m\ne n\: and\: m\ne2n\}=\{a^{\ast}b^{\ast}\}-\{a^nb^m|m=n\: or\: m=2n\}=\{a^nb^m|\: n>m\: or\: n<m\: or\: m>2n\: or\: m<2n\}[/tex]
در واقع اجتماع ۴ زبان مستقل از متن است و طبق بسته بودن زبان های مستقل از متن تحت اجتماع پس زبان اول مستقل از متن می باشد رد گزینه ۴ و جواب گزینه ۳

واقعا خسته نباشید. پاسخی دقیق و کامل.خیلی خوب بود.ایشالله موفق باشید.
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  گرامر منظم Sanazzz ۶ ۳۹۸ ۳۱ اردیبهشت ۱۳۹۸ ۰۴:۳۲ ب.ظ
آخرین ارسال: Sanazzz
  گرامر مستقل از متن Sanazzz ۴ ۵۳۹ ۱۲ دى ۱۳۹۷ ۰۹:۵۹ ب.ظ
آخرین ارسال: Sanazzz
Exclamation تشخیص نوع زبان و گرامر به صورت تستی و سریع kamran_maneshtir ۰ ۳۳۴ ۰۲ بهمن ۱۳۹۶ ۰۷:۴۶ ب.ظ
آخرین ارسال: kamran_maneshtir
  عبارت منظم fsmtnc ۱ ۳۳۹ ۲۱ دى ۱۳۹۶ ۰۶:۵۵ ب.ظ
آخرین ارسال: msour44
  گرامر منظم fsmtnc ۲ ۵۶۹ ۱۴ دى ۱۳۹۶ ۱۱:۵۷ ق.ظ
آخرین ارسال: fsmtnc
  حساس به متن و مستقل از متن kilookiloo ۲ ۶۹۴ ۰۶ اردیبهشت ۱۳۹۶ ۰۷:۴۱ ق.ظ
آخرین ارسال: kilookiloo
  بررسی چندمثال از کتاب شاپوری درخصوص منظم بودن ص۱۸۹ mzha ۱ ۵۴۷ ۲۸ فروردین ۱۳۹۶ ۰۶:۵۵ ب.ظ
آخرین ارسال: msour44
  تشخیص نوع زبان یک گرامر ali.majed.ha ۶ ۱,۲۲۳ ۲۷ فروردین ۱۳۹۶ ۰۹:۵۹ ب.ظ
آخرین ارسال: msour44
  تشخیص زبان مستقل ازمتن قطعی mzha ۲ ۶۷۲ ۲۲ دى ۱۳۹۵ ۱۰:۱۷ ب.ظ
آخرین ارسال: mzha
  زبان های نامتناهی hsehat ۳ ۱,۰۴۹ ۳۰ مهر ۱۳۹۵ ۰۴:۰۴ ب.ظ
آخرین ارسال: Pure Liveliness

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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