Изменения
В процессе редакции
{{Лемма
|id= ==lemma==
|about=о разрастании КС-грамматик
|statement=
Пусть <tex>L</tex> — [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободный язык]] над алфавитом <tex>\Sigma</tex>, тогда существует такое <tex>n</tex>, что для любого слова <tex> \omega \in L</tex> длины не меньше <tex>n</tex> найдутся слова <tex> u,v,x,y,z \in \Sigma^*</tex>, для которых верно: <tex>uvxyz=\omega, vy\neq \varepsilon, |vxy|\leqslant n</tex> и <tex>\forall k \geqslant 0~uv^{k}xy^{k}z\in L</tex>.
|proof=
[[Файл:Consp_lemma.png||left|240px|]] Пусть <tex>L</tex> — контекстно-свободный язык над алфавитом <tex>\Sigma</tex>. Тогда его грамматика может быть записана в [[Нормальная форма Хомского|нормальной форме Хомского (НФХ)]]. Пусть <tex>m</tex> — количество нетерминалов в полученной грамматике.
<br/> Выберем <tex>n=2^{m}</tex>. Построим дерево разбора слова <tex>\omega</tex>. Так как из одного нетерминала выводится либо два нетерминала, либо терминальный символ, то дерево разбора <tex>\omega</tex> будет бинарным, причем его высота не меньше <tex>m</tex>. Следовательно, по принципу Дерихле найдется такой нетерминал <tex>A</tex>, который раскрывается в дереве разбора дважды. Если таких нетерминалов несколько, то выберем нетерминал максимальной глубины, у которого в поддереве содержится такой же нетерминал. Тогда в качестве <tex>x</tex> выберем кратчайшую строку из терминалов, которая выводится из <tex>A</tex>.
|id= ==lemma==
|about=о разрастании КС-грамматик
|statement=
Пусть <tex>L</tex> — [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободный язык]] над алфавитом <tex>\Sigma</tex>, тогда существует такое <tex>n</tex>, что для любого слова <tex> \omega \in L</tex> длины не меньше <tex>n</tex> найдутся слова <tex> u,v,x,y,z \in \Sigma^*</tex>, для которых верно: <tex>uvxyz=\omega, vy\neq \varepsilon, |vxy|\leqslant n</tex> и <tex>\forall k \geqslant 0~uv^{k}xy^{k}z\in L</tex>.
|proof=
[[Файл:Consp_lemma.png||left|240px|]] Пусть <tex>L</tex> — контекстно-свободный язык над алфавитом <tex>\Sigma</tex>. Тогда его грамматика может быть записана в [[Нормальная форма Хомского|нормальной форме Хомского (НФХ)]]. Пусть <tex>m</tex> — количество нетерминалов в полученной грамматике.
<br/> Выберем <tex>n=2^{m}</tex>. Построим дерево разбора слова <tex>\omega</tex>. Так как из одного нетерминала выводится либо два нетерминала, либо терминальный символ, то дерево разбора <tex>\omega</tex> будет бинарным, причем его высота не меньше <tex>m</tex>. Следовательно, по принципу Дерихле найдется такой нетерминал <tex>A</tex>, который раскрывается в дереве разбора дважды. Если таких нетерминалов несколько, то выберем нетерминал максимальной глубины, у которого в поддереве содержится такой же нетерминал. Тогда в качестве <tex>x</tex> выберем кратчайшую строку из терминалов, которая выводится из <tex>A</tex>.
