Изменения
Нет описания правки
*Рассмотрим нетерминал <tex>A</tex>, содержащийся в поддереве выбранного нетерминала. Тогда <tex>x</tex> - строка терминалов которая выводится из рассмотренного нетерминала в данном дереве разбора. <tex>A \Rightarrow^{*} x</tex>.
*Рассмотрим выбранный нетерминал <tex>A</tex>. Пусть <tex>t</tex> - строка терминальных символов, которая выводится из рассмотренного нетерминала в данном дереве разбора. Тогда <tex>A \Rightarrow^{*}\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>.
*