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