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