در یک گرامر، به متغیری مانند $X$ ایلیچی گوییم، اگر حذف این متغیر از گرامر، باعث شود که زبان ساخته شده توسط گرامر تغییر کند. زبان $L$ را مجموعه‌ی تمام رشته‌هایی به صورت $\langle G, X \rangle$ در نظر بگیرید که $X$ یک متغیر ایلیچی در گرامر $G$ باشد.

1. ثابت کنید $L$ یک زبان تشخیص‌پذیر است. (۵۰ امتیاز)
2. ثابت کنید زبان $L$ تصمیم‌پذیر نیست. (۵۰ امتیاز)

• سوال بعد
• سوال قبل