حل تمرین نظریه محاسبات/فصل چهارم/حل تمرین ۴-۱۵

ویکی‎کتاب، کتابخانهٔ آزاد

تمرین ۴-۱۵

برای WWR یک گرامر مستقل از متن وجود دارد، این گرامر را G1 و زبان آن را L1 می‌نامیم

اشتراک L1 با زبان منظم این سوال یک زبان مستقل از متن L2 می‌باشد

با استفاده از تصمیم پذیر بودن Ecfg اثبات می‌شود که این مساله تصمیم پذیر است