http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=DmitryKarpovВикиконспекты - Вклад участника [ru]2026-05-07T22:44:38ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%9B%D0%B5%D0%BC%D0%BC%D0%B0_%D0%BE_%D1%80%D0%B0%D0%B7%D1%80%D0%B0%D1%81%D1%82%D0%B0%D0%BD%D0%B8%D0%B8_%D0%B4%D0%BB%D1%8F_%D0%9A%D0%A1-%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA&diff=13560Лемма о разрастании для КС-грамматик2011-11-27T02:23:40Z<p>DmitryKarpov: </p>
<hr />
<div>{{Лемма<br />
|id= ==lemma==<br />
|about=о разрастании КС-грамматик<br />
|statement=<br />
Пусть <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>.<br />
|proof=<br />
[[Файл:CS_lemma_conspect.PNG||left|240px|]] Пусть <tex>L</tex> — контекстно-свободный язык над алфавитом <tex>\Sigma</tex>. Тогда его грамматика может быть записана в [[Нормальная форма Хомского|нормальной форме Хомского (НФХ)]]. Пусть <tex>m</tex> — количество нетерминалов в полученной грамматике.<br />
<br/> Выберем <tex>n=2^{m}</tex>. Построим дерево разбора слова <tex>\omega</tex>. Так как из одного нетерминала выводится либо два нетерминала, либо терминальный символ, то дерево разбора <tex>\omega</tex> будет бинарным, причем его высота не меньше <tex>m</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 />
<br/> Таким образом, <tex>S =>^{*} uAz =>^{*} uvAyz =>^{*} uvvAyyz =>^{*} uv^{k}Ay^{k}z =>^{*} uv^{k}xy^{k}z</tex> <br />
}}</div>DmitryKarpovhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:CS_lemma_conspect.PNG&diff=13559Файл:CS lemma conspect.PNG2011-11-27T02:22:24Z<p>DmitryKarpov: Лемма о разрастании для КС-грамматик.</p>
<hr />
<div>Лемма о разрастании для КС-грамматик.</div>DmitryKarpov