Докажем, что <tex>\forall \Gamma \exists k: 0^k 1^k 2^k</tex> имеет хотя бы 2 дерева разбора.
{{Лемма
|statement=
<tex>\forall \Gamma : \exists k \ge 1: z \in L(\Gamma), |z| \ge k</tex> и в z выбраны хотябы k позиций, то z представимо в виде <tex>z = uvwxy</tex>, где <tex>uvw</tex> или <tex>wxy</tex> содержат хотя бы по одной выбранной позиции и <tex>vwx</tex> содержит не более k выбраных позиций и <tex>\exists A</tex> - нетерминал, такой, что <tex>\forall i: S \Rightarrow^* uAy \Rightarrow^* uvAxy \Rightarrow^* uv^i Ax^i y \Rightarrow^* uv^i wx^i y</tex>.
|proof=
Пусть в грамматике m нетерминалов, длина всех правых частей не превосходит l, значит высота дерева разбора хотя бы 2m+1.
Выбираем <tex>k=l^{2m+3}</tex>
Вершина ветвится, если хотя бы 2 ребенка.
Если есть сын с помечеными детьми в поддереве - идем в него, ветвится - идем где больше.
Вершина ветвится влево, если слева от него есть помеченные листья. Так же определяеся ветвление вправо.
Одного из этих типов хотя бы m+2.
Пусть m+2 ветвится влево. Рассмотрим нижние m+1 - среди них встретится повторяющийся нетерминал A. Для него уже выполнено условие леммы. В частности uvw - помечены. Из всех прочих выбираем один, в средней части не более k помеченных.
Лемма доказана.
}}
Неоднозначность:
Возьмем k, слово <tex>0^k 1^k 2^{k+k!}</tex>, пометим первые k нулей.
По [[Лемма Огдена|лемме Огдена]] можно разбить на 5 частей.
[[Файл:uvwxy.png]]
По лемме можно породить слово <tex>0^{k+k!} 1^{k+k!} 2^{k+k!}</tex>.
[[Файл:treetree2.png]] <tex>i = \frac{n!}{t} + 1</tex>
Аналогичные рассуждения справедливы для слова <tex>0^{k+k!} 1^k 2^k</tex>, в котором отмечены все двойки. Пусть в нем повторяющийся нетерминал B. Очевидно, что А и В - разные деревья и одно не является потомком другого.
