Изменения

Выберем путь от корня дерева к листу максимальной длины. Количество нетерминалов в нем не меньше, чем <tex>m+1</tex>, следовательно, найдется такой нетерминал <tex>B</tex>, который встречается на этом пути дважды. Значит, в дереве разбора найдется нетерминал <tex>B</tex>, в поддереве которого содержится нетерминал <tex>B</tex>. Выберем такой нетерминал <tex>A</tex> так, чтобы в его поддереве содержался такой же нетерминал и длина пути от него до корня была максимальна среди всех нетерминалов, содержащих в поддереве такой же нетерминал.

*Рассмотрим нетерминал <tex>A</tex>, содержащийся в поддереве выбранного нетерминала. Тогда <tex>x</tex> {{-- -}} строка терминалов, которая выведена из рассмотренного нетерминала в данном дереве разбора. Тогда <tex>A \Rightarrow^{*} x</tex>. *Рассмотрим выбранный ранее нетерминал <tex>A</tex>. Пусть <tex>t</tex> {{--- }} строка терминальных символов, которая выведена из рассмотренного нетерминала в данном дереве разбора. Тогда, так как выбранный нетерминал <tex>A</tex> содержит в своем поддереве такой же нетерминал, то <tex>A \Rightarrow^{*}\alpha A \beta \Rightarrow^{*} t</tex>, где <tex>\alpha,\beta</tex> - строки, которые могут содержать как терминалы, так и нетерминалы. При этом, как минимум одна из строк <tex>\alpha,\beta</tex> не пуста, так как грамматика языка записана в НФХ. Пусть <tex>v</tex> и <tex>y</tex> - строки, состоящие из терминалов, которые выведены соответственно из <tex>\alpha</tex> и <tex>\beta</tex>, в данном дереве разбора. Тогда <tex>t = vxy</tex>. Так как хотя бы одна из строк <tex>\alpha,\beta</tex> не пуста, то <tex>vy\neq \varepsilon</tex>. Получаем <tex>A \Rightarrow^{*} vAy \Rightarrow^{*} vxy</tex>.*Рассмотрим стартовый нетерминал <tex>S</tex>. Из <tex>S</tex> выведена строка <tex>\omega</tex>. При этом <tex>S \Rightarrow^{*} \alpha A \beta \Rightarrow^{*} \omega </tex>, где <tex>A</tex> {{--- }} выбранный ранее нетерминал. Из <tex>A</tex> в данном дереве разбора выведена строка <tex>vxy</tex>. Пусть <tex>u</tex> и <tex>z</tex> {{--- }} строки, состоящие из терминалов, которые выведены соответственно из <tex>\alpha</tex> и <tex>\beta</tex> в данном дереве разбора. Тогда <tex>S \Rightarrow^{*} uAz \Rightarrow^{*} uvAyz \Rightarrow^{*} \omega</tex>.