سلام دوستان، خسته نباشید
چنتا سوال بحث بر انگیز نظریه زبان داشتم؛ جوابشونا شک دارم، اگر ممکنه کمک کنید!
_ زبان های مستقل از متن تحت همریختی (همومورفیک) بسته نمی باشند؟؟ داخل کتاب نوشته هست، اما در تست سال ۸۵ و ... گفته نمیباشد!
_ زبان {WaZ| Z =! wR} (=! بمعنی غیر مساوی) و همچنین {(*wzwR| w,z E (a,b} (یعنی w,zرشته میباشند) مستقل ازمتن نمیباشند دیگه؟؟ چرا؟؟
با سلام دوست عزیز زبان های مستقل از متن تحت همریختی بسته هستن اما زبان ها مستقل از متن قطعی خیر
در مورد سوالتون اگر منظورتون از زبان اول اینه
[tex]\{ waz\: |\: z\ne\: w^R \}[/tex]
که این زبان مستقل از متن اما اگر a جز الفبای زبان نباشه مستقل از متن قطعی و اگر باشه غیر قطعی هست در حالت اول شما میگی W بریز تو پشته به a که رسیدی بریزش دور حال از بالا پشته پاپ کن و با بقیه قیاس کن اگر به یک حالت تناقض رسیدی که باهم برابر نبودن یعنی رشته پذیرفته میشه اگر تا ته رشته رفتیم و پشته خالی شد و به تناقض نرسیدیم رشته پذیرفته نمیشه
اما در حالت دوم مثل همینه اما غیر قعطی میگیم این کارو بکن چون نمیدونیم وسط رشته دقیقا کجاس و میگیم به وسط رشته رسیدی یک a بخون و بعد از a با بالای پشته قیاس کن باید یک تناقض پیدا کنیم بقیه اش مثل همون حالت اوله
اما زبان بعدی
[tex]\{ wzw^R\: |\: \: z,\: w\: \in\: Sigma\: ^{\ast\: } \}[/tex]
این زبان یک زبان منظم هستش و میدونیم هر زبان منظمی مستقل از متن قطعی پس مستقل از متن هم هست
چرا منظم؟ قبول دارید که رشته های که این زبان تولید می کنه زیر مجموعه از
[tex](a b)^{\ast}[/tex]
هستش؟ هر رشته ای تولید می کنه بلاخره یه تعدادی a یا b هستش دیگه
خوب حالا ایا قبول دارید که
[tex](a b)^{\ast}[/tex]
هم زیر مجموعه این هستش
[tex]\{ wzw^R\: |\: \: z,\: w\: \in\: Sigma\: ^{\ast\: } \}[/tex]
چون شما اینو
[tex](a b)^{\ast}[/tex]
Z در نظر بگیر
و w را هم رشته لاندا در نظر بگیر
زبان قبولش میکنه یا نه؟
خوب طبق ریاضی هم داریم
[tex]if\: A\subseteq\: B\: And\: B\subseteq\: A\: \longleftrightarrow\: A=\: B[/tex]
خوب زبان پس میشه
[tex](a b)^{\ast}[/tex]
که این زبانم میدونیم همون سیگما استار و منظم هست امیدوارم متوجه شده باشید موفق باشید
بسیار ممنونم از لطفتون دوست عزیز
بله؛ بسیار هم عالی توضیح دادید!
_منم مستقل ازمتن را نسبت به همریخته بسته میدونستم، اما در ۲ تست سراسری این چنین نبوده!
مثلا(سراسری ۸۵): کدام یک از عبارات زیر صحیح نمی باشد؟ (کتاب پوران گزینه ۲ را کلید اعلام کرده)
۱)الگوریتمی برای تصمیمگیری گرامر مستقل از متن((L(G) تهی است یا نه وجود دارد
۲)زبان های مستقل از متن تحت همریختی بسته
۳)زبان های خطی تحت همریختی بسته
۴)الگوریتمی برای تصمیمگیری گرامر مستقل از متن((L(G) متناهی است یا نه وجود دارد
_ چه توضیح قشنگی! ممنون. میشه یه راه کلی برای تشخیص مستقل از متن غیر قطعی و قطعی بگید؟؟ یکم گیج شدم وتسلطم کمه
مثلا WW^R غیر قطعی میباشد؟! چون به پشته غیر قطعی که وسط رشته را تشخیص بدیم نیاز داریم
_بله کاملا معلومه برابر Z* میباشد! بی دقتی کردم
بازم ممنون، همیشه موفق باشید
با سلام ببینید این تست که هر ۴ گزینه درسته حالا شاید توی این اشتباه تایپی هست بهتره برید کلید سنجش ببنید و یا از روی کتاب دیگه چک کنید کتاب پورانم بچه ها میگن خیلی غلط داره (ماله سهرابی) دیگه نمیدونم ولی این تستی که نوشتین هر ۴ گزینه درسته
اما در مورد زبان قطعی غیر قطعی راه حل قطعی نداریم و باید یه تجسمی بکنید از اینکه چطوری اون رشته هارو می پذیره و ایا هر مرحله که می خواهد ماشین کاری انجام بده یک راه مشخص داره یا نه
مثلا توی همینی که نوشتید چرا میگیم غیر قطعی؟ چون نمیدونه وسط رشته دقیقا کی هست و از کی باید شروع کنه از بالای پشته پاپ کردن و قیاس کردن
یا توی حالتی که
[tex]\{a^nb^n\}\: \: \cup\: \: \{a^nb^{2n}\}[/tex]
ماشین وقتی به b ها میرسه نمیدونه که باید به ازای هر یک b یک a پاپ کنه یا به ازای هر ۲ تا b یک a پس هیچ قطعیتی نیست و میگیم غیر قطعی تصمیم میگیره
البته نظریه هر چی بیشتر مدل ها و تایپ های مختلف ببینید زودتر مسلط میشید ولی خوب فک کنم بچه ها میگفتن توی کتاب پارسه چند صفحه ای زبان ها را خلاصه کرده شاید خوندنشون بد نباشه و اینکه واسه خودتون تحلیل کنید مثلا فلان زبان چطوری کار می کنه که قطعی یا غیر قطعی
دیگه چیز دیگه ای من به نظرم نمیرسه
موفق باشید
بسیار ممنون دوست عزیز از پاسخ های کاملتون
لطف کردید؛ همیشه شاد و موفق باشید