Изменения
→Существенно неоднозначные языки
Докажем, что для любой грамматики <tex>\Gamma</tex> <tex>\exists k: 0^k 1^k 2^k</tex> имеет хотя бы 2 дерева разбора в грамматике <tex>\Gamma</tex>.
Возьмем <tex>k </tex> и рассмотрим слово <tex>0^k 1^k 2^{k+k!}</tex>.
Пометим первые <tex>k</tex> нулей, по [[Лемма Огдена|лемме Огдена]] данное слово можно разбить на 5 частей: <tex>0^k1^k2^{k+k!}=uvxyz</tex>.
