سلام
اطفا راهنمایی کنید
فرض کنید زبان L1 , L2زبان های نوع دوم قطعی باشند . کدامیک از عبارات زیر غلط است
۱-L1UL2ممکن است زبان نوع دوم غیر قطعی باشد
۲-[tex]L={W|aW\epsilon L1 , a\epsilon \sum }{}[/tex]ممکن است یک زبان نوع دوم قطعی باشد.
۳-زبان [tex]\bar{L}[/tex] لزوما یک زبان نوع دوم قطعی نیست.
۴-[tex]L1\bigcap L2[/tex] ممکن است یم زبان نوع دوم غیر قطعی باشد
جواب زده گزینه یک
اما به نظرم گزینه ۳/۴ درسته
لطفا با دقت بخونید و مستدل نظر بدید نمی دونم سوال رو درست زدید یا نه من روش بحث میکنم ببینیم چند تا از گزینه ها درست و غلطه
این مثال لینز ویرایش سوم ص ۱۸۵ هستش [tex]L1=\left \{ a^{n}b^{n} , n\geq 0 \right \}[/tex] و [tex]L2=\left \{ a^{n}b^{2n} , n\geq 0 \right \}[/tex]
هر دو قطعی (قطعی بودن هر دو در کتاب لینز امده)هستند دقیقا کتاب لینز به اجتماع اشاره کرده و مستدل ثابت کرده اجتماع اینها غیر قطعی هستش اما...
اما [tex]L=\left \{ a^{n}b^{n},n\geq 1 \right \}\cup \left \{ a \right \}[/tex] که تمرین ۴ لینز ص ۱۸۷ هست میگه اجتماع دو زبان قطعی ، قطعی هست
لذا گزینه اول درست هست و جواب ما نمی تونه باشه
نکته : ببین بنابر قضیه(تمرین لینز ص ۱۸۸) هرگاه [tex]L1[/tex] نوع دوم قطعی و [tex]L2[/tex] منظم انگاه اجتماع حتما قطعی نوع دوم است
نکته : ببین بنابر قضیه(تمرین ۶ لینز ص ۱۸۷) هرگاه [tex]L1[/tex] نوع دوم قطعی آنگاه [tex]L^{*}[/tex] نوع دوم قطعی هست
در مورد گزینه ۲ : تمرین ۱۶ لینز ویرایش سوم ص ۲۰۷ ،همین تعریف رو آورده و گفته الزاما نوع دوم قطعی است این حالت قضیه داره ، پس گزینه ۲ غلطه .
گزینه ۳ و۴ هم به نظر من درست هستن و جواب ما نیست من سر جلسه بودم گزینه ۲ رو میزدم
خیلی ممنون از راهنمایتون
اشتباه من رو کلمات لزوما و ممکن است بود.گزینه ۳ رو زدم...با خودم گفتم تحت عمل مکمل بسته است...اما ممکن گفته...یعنی در شرایطی هم مکملش هم قطعی نمی شود که درست می شه
دقیقا درست متوجه شدید اینا رو بهش میگن بازی با کلمات بسیار باید مراقب بود
موفق باشید