حل تمرین نظریه محاسبات/فصل دوم/حل تمرین۲-۲۰

فرض کنید G یک گرامر مستقل از متن در فرم نرمال چامسکی با b نماد ناپایانه باشد. نشان دهید که اگر G بتواند رشته ای را با تعداد گام های اشتقاق بیشتر از b تولید کند آنگاه (L(G نامحدود است.

اثبات با کمک برهان خلف:

فرض خلف: (L(G محدود است.

اگر (L(G محدود باشد گرامر مستقل از متن G می بایست براساس تعداد محدودی از نمادهای ناپایانه همه رشته های زبان مورد نظر
را تشخیص دهد اما فرض مساله می گوید این CFG در فرم ساده شده نرمال چامسکی با b نماد ناپایانه در تناقض است چرا که
G قادر است رشته ای را با تعداد گام های اشتقاق بیشتر از b تولید کند و این نشان می دهد که رشته های این زبان محدود نیستند.