المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۷:ترکیبیات:سوال ۳

متغیرهای ایلیچی

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

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

ابزار صفحه