دستور زبان مستقل از متن: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
بدون خلاصۀ ویرایش |
بدون خلاصۀ ویرایش برچسب: ویرایش کاربر تازه‌کار |
||
خط ۲:
A→x که A € V و *(x € (V∪T
زبان L یک زبان مستقل از متن است اگر و تنها اگر گرامر مستقل از متنی مانند G وجود داشته باشد که رابطه ( L=L(G برقرار باشد.همه گرامرهای منظم مستقل از متن هستند؛ بنابراین یک
مثال‌های از زبان‌های مستقل از متن مثال یک: گرامر (S}،{a،b}،S،P}) با قانون‌های تولید s→aSa s→bSb s→Y مستقل از متن است. نمونه‌ای از یک اشتقاق در این گرامر به صورت s→aSa→aaSaa→aabSbaa→aabbaa می‌باشد. این اشتقاق و دیگر اشتقاق‌های مشابه نشان می‌دهند که زبان {L(G)={wwR:w€{a،b یک زبان مستقل از متن است؛ اما این زبان منظم نیست. مثال دو: s→abB A→aaBb B→bbAa A→Y مستقل از متن است. زبان متناظر با این گرامر {L(G)={ab(bbaa)^nbba(ba)^n:n>=0 می‌باشد. هر دوی این مثال‌ها گرامرهایی را نشان می‌دهند که علاوه بر مستقل از متن بودن، خطی نیز هستند. گرامرهای منظم و خطی مطمئناً مستقل از متن نیز می‌باشند. اما یک گرامر مستقل از متن لزوماً خطی نیست.<ref>نظریه زبان‌ها و ماشین‌ها پیتر لینز</ref>
| |||