Лемма о разрастании для КС-грамматик — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (лишнее слово)
Строка 6: Строка 6:
 
|proof=
 
|proof=
 
[[Файл:CS_lemma_conspect.PNG||left|240px|]] Пусть <tex>L</tex> — контекстно-свободный язык над алфавитом <tex>\Sigma</tex>. Тогда его грамматика может быть записана в [[Нормальная форма Хомского|нормальной форме Хомского (НФХ)]]. Пусть <tex>m</tex> — количество нетерминалов в полученной грамматике.
 
[[Файл: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>n=2^{m+1}</tex>. Построим дерево разбора произвольного слова <tex>\omega</tex> длиной больше, чем <tex>n</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>.
 
<br/> Таким образом, <tex>S \Rightarrow^{*} uAz \Rightarrow^{*} uvAyz \Rightarrow^{*} uvvAyyz \Rightarrow^{*} uv^{k}Ay^{k}z \Rightarrow^{*} uv^{k}xy^{k}z</tex>.
 
}}
 
}}

Версия 20:55, 23 января 2012

Лемма (о разрастании КС-грамматик):
Пусть [math]L[/math]контекстно-свободный язык над алфавитом [math]\Sigma[/math], тогда существует такое [math]n[/math], что для любого слова [math] \omega \in L[/math] длины не меньше [math]n[/math] найдутся слова [math] u,v,x,y,z \in \Sigma^*[/math], для которых верно: [math]uvxyz=\omega, vy\neq \varepsilon, |vxy|\leqslant n[/math] и [math]\forall k \geqslant 0~uv^{k}xy^{k}z\in L[/math].
Доказательство:
[math]\triangleright[/math]
CS lemma conspect.PNG
Пусть [math]L[/math] — контекстно-свободный язык над алфавитом [math]\Sigma[/math]. Тогда его грамматика может быть записана в нормальной форме Хомского (НФХ). Пусть [math]m[/math] — количество нетерминалов в полученной грамматике.


Выберем [math]n=2^{m+1}[/math]. Построим дерево разбора произвольного слова [math]\omega[/math] длиной больше, чем [math]n[/math]. Так как из одного нетерминала выводится либо два нетерминала, либо терминальный символ, то дерево разбора [math]\omega[/math] будет бинарным, причем его высота не меньше [math]m+1[/math]. Рассмотрим самый длинный путь от вершины, соответствующей стартовому нетерминалу,до листа. В нем будет не менее [math]m+1[/math] узлов, соответствующих нетерминалам. Следовательно, по принципу Дирихле найдется такой нетерминал [math]A[/math], который раскрывается в дереве разбора на этом пути дважды. Если таких путей и, следовательно, нетерминалов несколько, то выберем нетерминал максимальной глубины, у которого в поддереве содержится такой же нетерминал. Тогда в качестве [math]x[/math] выберем кратчайшую строку из терминалов, которая выводится из [math]A[/math]. Далее рассмотрим путь от предпоследнего повторения нетерминала [math] A[/math] до последнего его вхождения в дерево. Если из вершины был сделан переход в левое поддерево, то строка, выведенная из правого поддерева, будет частью [math]y[/math]. Аналогично из левых поддеревьев получаем [math]v[/math]. Так как грамматика записана в НФХ, то либо [math]v[/math], либо [math]y[/math] не будет пустой строкой, то есть условие [math]|vy|\gt 0[/math] выполнено.


Таким образом, [math]S \Rightarrow^{*} uAz \Rightarrow^{*} uvAyz \Rightarrow^{*} uvvAyyz \Rightarrow^{*} uv^{k}Ay^{k}z \Rightarrow^{*} uv^{k}xy^{k}z[/math].
[math]\triangleleft[/math]