Докажем, что для любой грамматики <tex>\Gamma</tex> <tex>\exists k: 0^k 1^k 2^k</tex> имеет хотя бы 2 дерева разбора в грамматике <tex>\Gamma</tex>.
Возьмем k и рассмотрим слово <tex>0^k 1^k 2^{k+k!}</tex>.
Возьмем Пометим первые k и рассмотрим нулей, по [[Лемма Огдена|лемме Огдена]] данное слово можно разбить на 5 частей: <tex>0^k 1k1^k 2k2^{k+k!}=uvxwz</tex>, где пометим первые k нулей.
По [[Лемма Огдена|лемме Огдена]] можно разбить данное Понятно, что <tex>v</tex> состоит полностью из нулей, а <tex>x</tex> состоит полностью из единиц, а также длины <tex>v</tex> и <tex>x</tex> равны, так как иначе при накачке мы можем получить слово на 5 частей, не принадлежащее языку.
[[Файл:uvwxyПусть <tex>|v|=|x|=t</tex>, тогда возьмём строку <tex>q=uv^{\frac{n!}{t} + 1}wx^{\frac{n!}{t} + 1}z=</tex>. По лемме Огдена слово <tex>q</tex> принадлежит языку, а также существует нетерминал <tex>A</tex> такой, что с помощью него можно породить слово <tex>q</tex>.png]]
По условию леммы есть нетерминал A - такой, что с помощью него можно породить слово <tex>0^{k+k!} 1^{k+k!} 2^{k+k!}</tex>[[Файл:tree2.png]]
[[Файл:tree2.png]] Теперь рассмотрим слово <tex>i = \frac0^{nk+k!}{t} + 1^k 2^k</tex>, в котором отмечены все двойки. Аналогичными рассуждениями мы получаем, что слово <tex>q</tex>принадлежит языку, а также существует нетерминал <tex>B<tex> такой, что с помощью него можно породить слово <tex>q</tex>.
Аналогичные рассуждения справедливы для слова <tex>0^{k+k!} 1^k 2^k</tex>, в котором отмечены все двойки. Пусть в нем повторяющийся нетерминал B.[[Файл:tree3.png]] <tex>i = \frac{n!}{t} + 1</tex>
Очевидно, что поддеревья, соответствующие <tex>А </tex> и <tex>В </tex> - разные деревья и одно не является потомком другого.
[[Файл:tree5.png]]
Тогда если Пусть в этих двух случай дерево разбора в обоих случаях одинаковобыло одно и тоже, то оно порождает слово вида <tex>0^{k+k!+s} 1^{k+k!+s+r} 2^{k+k!+r}</tex>, что которое не такпринадлежит языку.
В результате мы имеем 2 дерева разбора для одного слова. Значит язык существенно не однозначен.
{{Теорема
|statement=
Для языка принимаемого ДМП-автоматом существует однозначная КС-грамматика}}
