(۰۷ آذر ۱۳۹۲ ۱۱:۰۸ ق.ظ)zimenswall نوشته شده توسط:  دو تا تست در تستهای علوم کامپیوتر کتاب پوران دیدم که این دو مطلب را بیان کرده بود:
۱/ تشخیص تولید کلمه W توسط یک گرامر مستقل از متن یک مسئله تصمیم پذیر نیست
۲/ مسئله عضویت یک رشته در زبانهای مستقل از متن، تصمیم پذیر است

آیا این دو جمله با هم فرق دارند؟ و در کل مسئله عضویت برای مستقل از متن تصمیم پذیره یا نه؟

مسئله اول میگه که ما "آیا میتونیم یک کلمه رو با یک گرامر تولید کنیم یا نه" که این مصئله decidable نیست" توی کتاب لینز گفته"

مسله دوم یک کلمه به ما داده ما میخواییم بدونیم که این کلمه توی این زبان هست یا نه؟ چون زبان CFG هست یه گرامر CFG داره، فرض میکنیم که ما اون گرامر رو داریم، بعد اونو میکنیم فرم چامسکی که اینم امکان پذیره(با یه شرایط خاص) حالا یه الگوریتم به نام CYK از مرتبه $\mathcal{O}(|w|^3)$ وجود داره که به ما میگه ایا این کلمه در اون گرامر هست یا نه یا بهتر توی اون زبان هست یا نه!

(۰۷ آذر ۱۳۹۲ ۰۲:۰۱ ب.ظ)Riemann نوشته شده توسط:  

(07 آذر ۱۳۹۲ ۱۱:۰۸ ق.ظ)zimenswall نوشته شده توسط:  دو تا تست در تستهای علوم کامپیوتر کتاب پوران دیدم که این دو مطلب را بیان کرده بود:
۱/ تشخیص تولید کلمه W توسط یک گرامر مستقل از متن یک مسئله تصمیم پذیر نیست
۲/ مسئله عضویت یک رشته در زبانهای مستقل از متن، تصمیم پذیر است

آیا این دو جمله با هم فرق دارند؟ و در کل مسئله عضویت برای مستقل از متن تصمیم پذیره یا نه؟

مسئله اول میگه که ما "آیا میتونیم یک کلمه رو با یک گرامر تولید کنیم یا نه" که این مصئله decidable نیست" توی کتاب لینز گفته"

مسله دوم یک کلمه به ما داده ما میخواییم بدونیم که این کلمه توی این زبان هست یا نه؟ چون زبان CFG هست یه گرامر CFG داره، فرض میکنیم که ما اون گرامر رو داریم، بعد اونو میکنیم فرم چامسکی که اینم امکان پذیره(با یه شرایط خاص) حالا یه الگوریتم به نام CYK از مرتبه $\mathcal{O}(|w|^3)$ وجود داره که به ما میگه ایا این کلمه در اون گرامر هست یا نه یا بهتر توی اون زبان هست یا نه!

تشکر از شما
زیادی مفهومی بود، یا بهتره بگم فلسفی بود. ولی با توضیحات خوب شما بالاخره فهمیدم