Изменения
Нет описания правки
Выберем <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>AB</tex>, который раскрывается в дереве разбора встречается на этом пути дважды. Если таких путей иЗначит, следовательно, нетерминалов несколько, то выберем в дереве разбора найдется нетерминал максимальной глубины<tex>B</tex>, у которого в поддереве которого содержится такой же нетерминал. Тогда в качестве <tex>xB</tex> выберем кратчайшую строку из терминалов, которая выводится из . Выберем нетерминал <tex>A</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>.
}}
