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

تمرین ۴-۱۵

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

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

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