Изменения
Нет описания правки
==Лемма о разрастании для КС-грамматик==
{''{Лемма
|id= ==lemma==
|about=о разрастании КС-грамматик
Выберем <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 \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,z</tex> - строки, состоящие из терминалов, которые выведены из <tex>\alpha,\beta</tex> соответственно, в данном дереве разбора. Тогда <tex>S \Rightarrow^{*} uAz \Rightarrow^{*} uvAyz \Rightarrow^{*} \omega</tex>.
