Выберем <tex>n=2^{m+1}</tex>. Построим дерево разбора произвольного слова <tex>\omega</tex> длиной больше, чем <tex>n</tex>. Высотой дерева разбора назовем максимальное число нетерминальных символов на пути от корня дерева к листу. Так как грамматика языка <tex>L</tex> записана в НФХ, то у любого нетерминала в дереве могут быть, либо два потомка нетерминала, либо один потомок терминал. Поэтому высота дерева разбора слова <tex>\omega</tex> не меньше <tex>m+1</tex>.
Рассмотрим самый длинный путь от вершины дерева разбора до листа. Количество нетерминалов в нем не меньше, чем <tex>m+1</tex>, следовательно, найдется такой нетерминал <tex>B</tex>, который встречается на этом пути дважды. Значит, в дереве разбора найдется нетерминал <tex>B</tex>, в поддереве которого содержится нетерминал <tex>B</tex>. Выберем нетерминал <tex>A</tex>, у которого в поддереве содержится такой же нетерминал и длина пути до корня максимальна среди всех нетерминалов, содержащих в поддереве такой же нетерминал.
Далее Найдем слова <tex> u,v,x,y,z </tex>. *Рассмотрим нетерминал <tex>A</tex>, содержащийся в поддереве выбранного нетерминала. Тогда <tex>x</tex> - строка терминалов которая выводится из <tex>A</tex>. <tex>A \Rightarrow^{*} x</tex>. рассмотрим путь от предпоследнего повторения нетерминала <tex> A</tex> до последнего его вхождения в дерево. Если из вершины был сделан переход в левое поддерево, то строка, выведенная из правого поддерева, будет частью <tex>y</tex>. Аналогично из левых поддеревьев получаем <tex>v</tex>. Так как грамматика записана в НФХ, то либо <tex>v</tex>, либо <tex>y</tex> не будет пустой строкой, то есть условие <tex>|vy|>0</tex> выполнено.
Таким образом, <tex>S \Rightarrow^{*} uAz \Rightarrow^{*} uvAyz \Rightarrow^{*} uvvAyyz \Rightarrow^{*} uv^{k}Ay^{k}z \Rightarrow^{*} uv^{k}xy^{k}z</tex>.
}}
