Plan dowodu jest następujący: Zakładamy nie wprost, że język jest bezkontekstowy. Z lematu o pompowaniu bierzemy stałą Budujemy słowo być może zależne od Pokazujemy, że niezależnie od podziału słowa na dla pewnego słowo nie należy do badanego języka. W ten sposób otrzymujemy sprzeczność i kończymy dowód nie wprost.
Zobacz też lemat o pompowaniu dla języków regularnych
Przypisy
Kategoria:Języki formalne O