سلام دوستان
باتوجه به اینکه برای هر گرامر بدون محدودیت، یک گرامر معادل وجود داره که همه ی قوانینش رو بتونیم به شکل زیر تبدیل کنیم:
u --> v
|u| <= |v|
و این قوانینی که بالا گفته شد، مربوط به گرامر کران دار هستش، پس چرا قدرت این ۲تا زبان با هم فرق میکنه؟
اینکه برای هر گرامر بدون محدودیت میشه قوانین بالا رو اعمال کرد من توی لینز همچین تمرینی دیده بودم...
(۰۳ بهمن ۱۳۹۲ ۱۱:۲۶ ب.ظ)El@he نوشته شده توسط: سلام دوستان
باتوجه به اینکه برای هر گرامر بدون محدودیت، یک گرامر معادل وجود داره که همه ی قوانینش رو بتونیم به شکل زیر تبدیل کنیم:
u --> v
|u| <= |v|
و این قوانینی که بالا گفته شد، مربوط به گرامر کران دار هستش، پس چرا قدرت این ۲تا زبان با هم فرق میکنه؟
اینکه برای هر گرامر بدون محدودیت میشه قوانین بالا رو اعمال کرد من توی لینز همچین تمرینی دیده بودم...
گرامر بدون محدودیت
[tex]u \rightarrow v | u \in (V\cup T)^ , v \in (V\cup T)^*[/tex]
گرامر حساس به متن (همون LBA)
[tex]u \rightarrow v | u \in (V\cup T)^ , v \in (V\cup T)^ [/tex]
بخاطر همینه که گرامر حساس انتقال لاندا نداریم (البته تو زبانش رشته تهی داریم) ولی تو گرامر بدون محدودیت انتقال لاندا داریم
همین یه جمله عدم برابری این دوتا رو میرسونه
(۰۳ بهمن ۱۳۹۲ ۱۱:۵۳ ب.ظ)masoud67 نوشته شده توسط:(03 بهمن ۱۳۹۲ ۱۱:۲۶ ب.ظ)El@he نوشته شده توسط: سلام دوستان
باتوجه به اینکه برای هر گرامر بدون محدودیت، یک گرامر معادل وجود داره که همه ی قوانینش رو بتونیم به شکل زیر تبدیل کنیم:
u --> v
|u| <= |v|
و این قوانینی که بالا گفته شد، مربوط به گرامر کران دار هستش، پس چرا قدرت این ۲تا زبان با هم فرق میکنه؟
اینکه برای هر گرامر بدون محدودیت میشه قوانین بالا رو اعمال کرد من توی لینز همچین تمرینی دیده بودم...
گرامر بدون محدودیت
[tex]u \rightarrow v | u \in (V\cup T)^ , v \in (V\cup T)^*[/tex]
گرامر حساس به متن (همون LBA)
[tex]u \rightarrow v | u \in (V\cup T)^ , v \in (V\cup T)^ [/tex]
بخاطر همینه که گرامر حساس انتقال لاندا نداریم (البته تو زبانش رشته تهی داریم) ولی تو گرامر بدون محدودیت انتقال لاندا داریم
همین یه جمله عدم برابری این دوتا رو میرسونه
منم حدس زدم به خاطر لاندا باشه ولی با تورینگ کران دار خطی (ماشین حساس به متن) حس میکنم لاندا پذیرفته است. پس یه جورای خودمون توی تعریفش میگیم ماشین کران دار خطی باشه و لاندا رو نپذیره!؟
(۰۴ بهمن ۱۳۹۲ ۱۲:۱۴ ق.ظ)El@he نوشته شده توسط:خطر خطر(03 بهمن ۱۳۹۲ ۱۱:۵۳ ب.ظ)masoud67 نوشته شده توسط: بخاطر همینه که گرامر حساس انتقال لاندا نداریم (البته تو زبانش رشته تهی داریم) ولی تو گرامر بدون محدودیت انتقال لاندا داریممنم حدس زدم به خاطر لاندا باشه ولی با تورینگ کران دار خطی (ماشین حساس به متن) حس میکنم لاندا پذیرفته است. پس یه جورای خودمون توی تعریفش میگیم ماشین کران دار خطی باشه و لاندا رو نپذیره!؟
ماشین کراندار لاندا رو میپذیره . من گفتم در گرامر حساس انتقال لاندا نداریم نگفتم زبان لاندا نداریم. حساس میتونه لاندا رو بپذیره کی ؟؟؟؟
زمانی که حالت شروع ماشین کران دار خطی حالت نهایی باشه . ولی وقتی گرامر حساس مینویسیم نمیتونیم انتقال لاندا داشته باشیم
(۰۴ بهمن ۱۳۹۲ ۱۲:۲۴ ق.ظ)masoud67 نوشته شده توسط:(04 بهمن ۱۳۹۲ ۱۲:۱۴ ق.ظ)El@he نوشته شده توسط:خطر خطر(03 بهمن ۱۳۹۲ ۱۱:۵۳ ب.ظ)masoud67 نوشته شده توسط: بخاطر همینه که گرامر حساس انتقال لاندا نداریم (البته تو زبانش رشته تهی داریم) ولی تو گرامر بدون محدودیت انتقال لاندا داریممنم حدس زدم به خاطر لاندا باشه ولی با تورینگ کران دار خطی (ماشین حساس به متن) حس میکنم لاندا پذیرفته است. پس یه جورای خودمون توی تعریفش میگیم ماشین کران دار خطی باشه و لاندا رو نپذیره!؟
ماشین کراندار لاندا رو میپذیره . من گفتم در گرامر حساس انتقال لاندا نداریم نگفتم زبان لاندا نداریم. حساس میتونه لاندا رو بپذیره کی ؟؟؟؟
زمانی که حالت شروع ماشین کران دار خطی حالت نهایی باشه . ولی وقتی گرامر حساس مینویسیم نمیتونیم انتقال لاندا داشته باشیم
آخه مگه کران دار خطی معادل با گرامر حساس به متن نیست؟!
پس اینجوری میگیم: با فرض اینکه گرامر حساس به متن، رشته ی لاندا رو بپذیره، معادل با کران دار خطی میشه، درسته؟
(۰۴ بهمن ۱۳۹۲ ۱۲:۲۹ ق.ظ)El@he نوشته شده توسط: آخه مگه کران دار خطی معادل با گرامر حساس به متن نیست؟!درسته. هر گرامری حساس ، یک زبان خطی است. و بالعکس، البته به جز لاندا.
پس اینجوری میگیم: با فرض اینکه گرامر حساس به متن، رشته ی لاندا رو بپذیره، معادل با کران دار خطی میشه، درسته؟
زبان را حساس به متن میگیم اگه یه گرامر حساس به متنی واسش باشه
و هر زبانی که توسط یه ماشین کراندار خطی پذیرفته بشه براش یک گرامر حساس هست
یه چیز تو مایه های چامسکی میشه که هر وقت یه قضیه براش میگن سریع سر و کله لاندا پیدا میشه و استثنا میشه واسه اون قضیه