Изменения

|id= ==lemma==

[[Файл:CS_lemma_conspect.PNG||left|240px|]] Пусть <tex>L</tex> — Грамматика любого контекстно-свободный язык над алфавитом <tex>\Sigma</tex>. Тогда его грамматика свободного языка может быть записана в [[Нормальная форма Хомского|нормальной форме Хомского (НФХ)]]. Пусть <tex>m</tex> — количество нетерминалов в полученной грамматике.языка <tex>L<br/tex> , записанной в НФХ.Выберем <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>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>y\alpha,\beta</tex>- строки, которые могут содержать как терминалы, так и нетерминалы. Аналогично При этом как минимум одна из левых поддеревьев получаем строк <tex>v\alpha,\beta</tex>. Так не пуста, так как грамматика языка записана в НФХ. Пусть <tex>v</tex> и <tex>y</tex> - строки, то либо состоящие из терминалов, которые выведены соответственно из <tex>\alpha</tex> и <tex>v\beta</tex>, либо в данном дереве разбора. Тогда <tex>t = vxy</tex>. Так как хотя бы одна из строк <tex>y\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>. Покажем, что <tex>|vxy| \leqslant n</tex>. Допустим, что <tex>|vyvxy|>0n</tex>. Тогда высота поддерева с корнем в вершине, соответствующей выбранному <tex>A</tex>, не меньше <tex>m+2</tex>. Рассмотрим поддерево вершины, в котором содержится нетерминал <tex>A</tex>. Тогда высота этого поддерева не меньше <tex>m+1</tex>. Рассмотрим путь максимальной длины от корня этого поддерева к листу. В нем содержится не менее <tex>m+1</tex> выполненонетерминалов, причем не содержится стартовый нетерминал.Следовательно, на этом пути найдутся два одинаковых нетерминала, что противоречит условию наибольшей удаленности от корня выбранного ранее нетерминала <tex>A</tex>. Получили противоречие. Поэтому <tex>|vxy|\leqslant n<br/tex> .Таким образом, в рамках нашей грамматики мы можем построить цепочку вывода: <tex>S \Rightarrow^{*} uAz \Rightarrow^{*} uvAyz \Rightarrow^{*} uvvAyyz \Rightarrow^{*} uv^{k}Ay^{k}z \Rightarrow^{*} uv^{k}xy^{k}z</tex> .