تالار گفتمان مانشت
تعیین نوع زبان( مستقل از متن یا منظم) ازمون های آزمایشی - نسخه‌ی قابل چاپ

تعیین نوع زبان( مستقل از متن یا منظم) ازمون های آزمایشی - AZ_AMIR - 02 اردیبهشت ۱۳۹۶ ۰۱:۳۲ ب.ظ

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

RE: تعیین نوع زبان( مستقل از متن یا منظم) ازمون های آزمایشی - msour44 - 02 اردیبهشت ۱۳۹۶ ۰۹:۰۰ ب.ظ

سلام
اول منظم بودن [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]
در واقع اجتماع ۴ زبان مستقل از متن است و طبق بسته بودن زبان های مستقل از متن تحت اجتماع پس زبان اول مستقل از متن می باشد رد گزینه ۴ و جواب گزینه ۳

RE: تعیین نوع زبان( مستقل از متن یا منظم) ازمون های آزمایشی - AZ_AMIR - 03 اردیبهشت ۱۳۹۶ ۰۷:۵۳ ب.ظ

(۰۲ اردیبهشت ۱۳۹۶ ۰۹:۰۰ ب.ظ)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]
در واقع اجتماع ۴ زبان مستقل از متن است و طبق بسته بودن زبان های مستقل از متن تحت اجتماع پس زبان اول مستقل از متن می باشد رد گزینه ۴ و جواب گزینه ۳

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