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