سلام
سوال این بوده چندتااز زبان های زیر مستقل از متن هس جواب هرسه تا نوشته چراl2مستقل از متنه؟
با سلام دوست عزیز دقت کنید زبان دوم گفته
w1 مخالف w2 باشه اگر گفته بود مساوی باشن مستقل از متن نبود چون وقتی رشته را پیمایش کنید عنصر اول w1 میره اخر پشته و عنصر اخر میاد بالای پاشته پس ما نمی تونیم عنصر اول با اول دوم با دوم ... قیاس کنیم پس مستقل از متن نیست
اما دقت کنید داره میگه مخالف هم باشن چه وقتی مخالف همدیگه هستن؟ وقتی حداقل توی یک حرف حداقل تناقض داشته باشن دیگه مثلا عنصر K ام رشته اول با عنصر K ام رشته دوم مخالف باشه خوب دقت کنید وقتی دو رشته بخواهن مساوی باشن طولشون هم برابره دیگه
حالا ما به طور غیر قطعی میگیم مثلا فلان عنصر (عنصر K ام ) رشته اول با رشته دوم قیاس کن مخالف بودن پس رشته اکسپت میشه هر دفعه به طور غیر قطعی مثلا میگیم عنصر چهارم با چهارم اون قیاس کن میاد و رشته اول تا عنصر ۴ میریزه تو پشته و بقیه اشو میریزه دور و رشته دوم هم ۳ تا اولشو میریزه دور و ۴ با بالای پشته قیاس میکنه اگر تناقض داشت اکسپت میشه دقت کنید مستقل از متن غیر قطعی هستش به خاطر همین غیر قطعی هست که ما نمیدونیم دقیقا کدوم عنصر با کدوم قیاس کنیم بهتر می خواید متوجه شید فک کنم دکتر گارگهی توی جزوه اشون توضیح دادن توی سایت هست دانلود کنید بخونید موفق باشید
این سوال قبلا هم تو تاپیک های بحث شده (به تاپیک های بخش پرسش و پاسخ مراجعه شود)
اما تازگیا یه جواب خوب شسته رفته واسه این سوال دیدم:
دو زبان منظم زیر را در نظر بگیرید:
[tex]D=\{x\in(a,b)^{\ast},\: |x|\: is\: odd\}[/tex]
[tex]E=\{x\in(a,b)^{\ast},\: |x|\: is\: even\}[/tex]
D زبان تمام رشته ای به طول فرد و E زبان تمام رشته های به طول زوج
[tex]K=\{ww|w\in(a,b)^{\ast}\}[/tex]
این L2 ای که شما فرمودید را می شه به این صورت نوشت:
[tex]L2=D\cup(E-K)[/tex]
D که منظمه کافیه نشون بدیم E-K هم مستقل از متنه تا اجتماعشون مستقل از متن بشه
E-k را می توان به این صورت نوشت:
[tex]E-K=\{uawbv|\: u,v,w\in\{a,b\}^{\ast},\: |u| |v|=|w|\}\cup\{ubwav|\: u,v,w\in\{a,b\}^{\ast},\: |u| v|=|w|\}[/tex]
و واضح است که هر دو قسمت آن مستقل از متن هستند
مرسی از جواب دوستان اقای حمید چرا از رشته دوم بقیشودور میریزه ومثلا عنصر۴رو مقایسه میکنه؟میشه لطفا با یه مثال توضیح بدیدهم براحالتی که مساوین هم حالتی که مساوی نیستن بعد این جزوه اقای هاتف منظورتونه ؟توضیح زیادی که نداره
دوست عزیز توضیحات بالارو بخونید گفتیم غیر قطعی میاد و مثلا میگه عنصر K رشته اول با K ام رشته دوم مقایسه کن مخالف بودن یعنی پذیرفته میشه حالا این k من مثلا برای توضیح گفتم عدد ۴ میتونه ۵ باشه ۶ باشه ۷ باشه هر چی اونو غیر قطعی ماشین انتخاب می کنه
ببیند برای تساوی دو تا رشته باید تمام عناصر باهم برابر باشن اما برای عدم تساوی یک تناقض هم کافیه یعنی کافیه مثلا حرف ۴ دوتا رشته با هم فرق داشته باشه وقتی عنصر ۴ دوتا رشته فرق داره بقیه اشونم که مساوی باشه بازم دو رشته مساوین؟ نه نیستن پس ماشین کافیه یه تناقض پیدا کنه تو رشته به خاطر همین میگیم غیر قطعی عنصر K ام قیاس کن
منظور از دور ریختنم اینه که از رشته اول بقیه اشو مثلا تو پشته نمیریزه و از رشته دوم هم اون اولشو با پشته قیاس نمی کنه اگر دور نریزه که نمی تونه عنصر K ام رشته اول با رشته دوم مقایسه کنه
در حد لازم فک می کنم همون جزوه کافیه چیز سختی نیست البته شاید تو ویسش توضیحات بیشتری باشه