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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (опечатка)
(не показано 35 промежуточных версий 8 участников)
Строка 1: Строка 1:
 +
__FORCETOC__
 +
== Лемма о разрастании для КС-грамматик ==
 +
 
{{Лемма
 
{{Лемма
|id= ==lemma==
+
|id=lemma
 
|about=о разрастании КС-грамматик
 
|about=о разрастании КС-грамматик
 
|statement=
 
|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>.
 
Пусть <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=
 
|proof=
[[Файл:CS_lemma_conspect.PNG||left|240px|]] Пусть <tex>L</tex> — контекстно-свободный язык над алфавитом <tex>\Sigma</tex>. Тогда его грамматика может быть записана в [[Нормальная форма Хомского|нормальной форме Хомского (НФХ)]]. Пусть <tex>m</tex> — количество нетерминалов в полученной грамматике.
+
[[Файл:CS_lemma_conspect.PNG||left|240px|]] Грамматика любого контекстно-свободного языка может быть записана в [[Нормальная форма Хомского|нормальной форме Хомского (НФХ)]]. Пусть <tex>m</tex> — количество нетерминалов в грамматике языка <tex>L</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> выполнено.
+
Выберем <tex>n=2^{m+1}</tex>. Построим дерево разбора произвольного слова <tex>\omega</tex> длиной больше, чем <tex>n</tex>.  Высотой дерева разбора назовем максимальное число нетерминальных символов на пути от корня дерева к листу. Так как грамматика языка <tex>L</tex> записана в НФХ, то у любого нетерминала в дереве могут быть, либо два потомка нетерминала, либо один потомок терминал. Поэтому  высота дерева разбора слова <tex>\omega</tex> не меньше <tex>m+1</tex>.
<br/> Таким образом, <tex>S \Rightarrow^{*} uAz \Rightarrow^{*} uvAyz \Rightarrow^{*} uvvAyyz \Rightarrow^{*} uv^{k}Ay^{k}z \Rightarrow^{*} uv^{k}xy^{k}z</tex>  
+
 
 +
Выберем путь от корня дерева к листу максимальной длины. Количество нетерминалов в нем не меньше, чем <tex>m+1</tex>, следовательно, найдется такой нетерминал <tex>B</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>\alpha,\beta</tex> - строки, которые могут содержать как терминалы, так и нетерминалы. При этом как минимум одна из строк <tex>\alpha,\beta</tex> не пуста, так как грамматика языка записана в НФХ. Пусть <tex>v</tex> и <tex>y</tex> - строки, состоящие из терминалов, которые выведены  соответственно из <tex>\alpha</tex> и <tex>\beta</tex>, в данном дереве разбора. Тогда <tex>t = vxy</tex>. Так как хотя бы одна из строк <tex>\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>|vxy|>n</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</tex>.
 +
Таким образом, в рамках нашей грамматики мы можем построить цепочку вывода: <tex>S \Rightarrow^{*} uAz \Rightarrow^{*} uvAyz \Rightarrow^{*} uvvAyyz \Rightarrow^{*} uv^{k}Ay^{k}z \Rightarrow^{*} uv^{k}xy^{k}z</tex>.
 
}}
 
}}
 +
 +
'''Замечание.''' Условие леммы не является достаточным для контекстно-свободности языка. Но, в силу необходимости условия, данная лемма часто используется для доказательства неконтекстно-свободности языков.
 +
 +
== Пример доказательства неконтекстно-свободности языка с использованием леммы ==
 +
 +
Рассмотрим язык <tex>0^{n}1^{n}2^{n}</tex>. Покажем, что он не является контекстно-свободным.
 +
 +
Для фиксированного <tex>n</tex> рассмотрим слово <tex>\omega=0^n 1^n 2^n</tex>. Пусть <tex>\omega</tex> разбили на <tex>u, v, x, y, z</tex> произвольным образом. Так как <tex>|vxy|\leqslant n</tex>, то в слове  <tex>vxy</tex> не содержится либо ни одного символа <tex>0</tex>, либо ни одного символа <tex>2</tex>. Для любого такого разбиения выбираем <tex>k=2</tex> и получаем, что количество символов <tex>1</tex> изменилось, а количество либо <tex>0</tex>, либо <tex>2</tex> осталось тем же. Очевидно, что такое слово не принадлежит рассмотренному языку. Значит, язык <tex>0^{n}1^{n}2^{n}</tex> не является контекстно-свободным по лемме о разрастании для КС-грамматик.
 +
 +
== Пример не КС-языка, для которого выполняется лемма ==
 +
 +
Рассмотрю язык <tex>L=\{a^{n}b^{n}c^{i}\mid i \neq n\}</tex>.
 +
 +
'''Докажем, что он не контекстно-свободный'''. Для этого воспользуемся [[Лемма_Огдена|леммой Огдена]]. Для фиксированного <tex>n</tex> рассмотрим слово <tex>\omega=a^n b^n c^{n!+n}</tex>. Пометим все символы <tex>a</tex> и <tex>b</tex>. Пусть <tex>\omega</tex> разбили на <tex>u, v, x, y, z</tex>, так что <tex>x</tex> содержит выделенную позицию; <tex>u</tex> и <tex>v</tex> содержат выделенные позиции и <tex>vxy</tex> содержат не более <tex>n</tex> выделенных позиций. Тогда очевидно, что <tex>vy</tex> должно содержать одинаковое число символов <tex>a</tex> и <tex>b</tex>, иначе выбираем <tex>k=0</tex> и тогда количество символов <tex>a</tex> и <tex>b</tex> станет разным. Пусть символов <tex>a</tex> в <tex>vy</tex> будет <tex>t</tex>. Так же очевидно, что <tex>vy</tex> не содержит символов <tex>c</tex>, так как <tex>vxy</tex> содержат не более <tex>n</tex> выделенных позиций, но <tex>v</tex> точно содержит символ <tex>a</tex>. Тогда выберем <tex>k=\dfrac{n!}{t}+1</tex> и получим слово <tex>a^{n!+n}b^{n!+n}c^{n!+n}</tex>, которое не принадлежит рассмотренному языку. Значит <tex>a^{n}b^{n}c^{i}</tex> не является контекстно-свободным.
 +
 +
'''Докажем, что язык удовлетворяет лемме о разрастании'''. Выберем <tex>n=5</tex>. Это значит, что длина рассматриваемых слов не меньше <tex>3</tex>. Рассмотрим случаи:
 +
# <tex>c^i</tex>
 +
#:Выберем <tex>u=c^{i-1}</tex>, <tex>v=c</tex>, <tex>x=y=z=\varepsilon</tex>.
 +
# <tex>a^jb^j</tex>
 +
#:Выберем <tex>u=a^{j-1}</tex>, <tex>v=a</tex>, <tex>x=\varepsilon</tex>, <tex>y=b</tex>, <tex>z=b^{j-1}</tex>.
 +
# <tex>a^jb^jc^i</tex>, где <tex>i < j-1</tex>
 +
#:Выберем <tex>u=a^{j-1}</tex>, <tex>v=a</tex>, <tex>x=\varepsilon</tex>, <tex>y=b</tex>, <tex>z=b^{j-1}c^i</tex>.
 +
# <tex>a^jb^jc^{j-1}</tex>
 +
#:Выберем <tex>u=a^{j-2}</tex>, <tex>v=aa</tex>, <tex>x=\varepsilon</tex>, <tex>y=bb</tex>, <tex>z=b^{j-2}c^i</tex>.
 +
# <tex>a^jb^jc^{j+1}</tex>
 +
#:Выберем <tex>u=a^{j-2}</tex>, <tex>v=aa</tex>, <tex>x=\varepsilon</tex>, <tex>y=bb</tex>, <tex>z=b^{j-2}c^i</tex>.
 +
# <tex>a^jb^jc^i</tex>, где <tex>i>j+1</tex>
 +
#:Выберем <tex>u=a^jb^jc^{i-1}</tex>, <tex>v=c</tex>, <tex>x=y=z=\varepsilon</tex>.
 +
 +
Таким образом язык <tex>L</tex> '''не''' контекстно-свободный, но удовлетворяет второй части леммы.
 +
 +
== См. также ==
 +
* [[Лемма_Огдена|Лемма Огдена]]
 +
 +
== Источники ==
 +
 +
* Хопкрофт Д., Мотвани Р., Ульман Д. {{---}} Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. {{---}} Москва, Издательский дом «Вильямс», 2002. {{---}} 528 с. : ISBN 5-8459-0261-4 (рус.)
 +
 +
[[Категория: Теория формальных языков]]
 +
[[Категория: Контекстно-свободные грамматики]]
 +
[[Категория: Опровержение контекстно-свободности языка]]

Версия 23:00, 6 ноября 2016

Лемма о разрастании для КС-грамматик

Лемма (о разрастании КС-грамматик):
Пусть [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]m[/math] — количество нетерминалов в грамматике языка [math]L[/math], записанной в НФХ.

Выберем [math]n=2^{m+1}[/math]. Построим дерево разбора произвольного слова [math]\omega[/math] длиной больше, чем [math]n[/math]. Высотой дерева разбора назовем максимальное число нетерминальных символов на пути от корня дерева к листу. Так как грамматика языка [math]L[/math] записана в НФХ, то у любого нетерминала в дереве могут быть, либо два потомка нетерминала, либо один потомок терминал. Поэтому высота дерева разбора слова [math]\omega[/math] не меньше [math]m+1[/math].

Выберем путь от корня дерева к листу максимальной длины. Количество нетерминалов в нем не меньше, чем [math]m+1[/math], следовательно, найдется такой нетерминал [math]B[/math], который встречается на этом пути дважды. Значит, в дереве разбора найдется нетерминал [math]B[/math], в поддереве которого содержится нетерминал [math]B[/math]. Выберем такой нетерминал [math]A[/math], чтобы в его поддереве содержался такой же нетерминал и длина пути от него до корня была максимальна среди всех нетерминалов, содержащих в поддереве такой же нетерминал.

Найдем слова [math] u,v,x,y,z [/math].

  • Рассмотрим нетерминал [math]A[/math], содержащийся в поддереве выбранного нетерминала. Тогда [math]x[/math] — строка терминалов, которая выведена из рассмотренного нетерминала в данном дереве разбора. Тогда [math]A \Rightarrow^{*} x[/math].
  • Рассмотрим выбранный ранее нетерминал [math]A[/math]. Пусть [math]t[/math] — строка терминальных символов, которая выведена из рассмотренного нетерминала в данном дереве разбора. Тогда, так как выбранный нетерминал [math]A[/math] содержит в своем поддереве такой же нетерминал, то [math]A \Rightarrow^{*}\alpha A \beta \Rightarrow^{*} t[/math], где [math]\alpha,\beta[/math] - строки, которые могут содержать как терминалы, так и нетерминалы. При этом как минимум одна из строк [math]\alpha,\beta[/math] не пуста, так как грамматика языка записана в НФХ. Пусть [math]v[/math] и [math]y[/math] - строки, состоящие из терминалов, которые выведены соответственно из [math]\alpha[/math] и [math]\beta[/math], в данном дереве разбора. Тогда [math]t = vxy[/math]. Так как хотя бы одна из строк [math]\alpha,\beta[/math] не пуста, то [math]vy\neq \varepsilon[/math]. Получаем [math]A \Rightarrow^{*} vAy \Rightarrow^{*} vxy[/math].
  • Рассмотрим стартовый нетерминал [math]S[/math]. Из [math]S[/math] выведена строка [math]\omega[/math]. При этом [math]S \Rightarrow^{*} \alpha A \beta \Rightarrow^{*} \omega [/math], где [math]A[/math] — выбранный ранее нетерминал. Из [math]A[/math] в данном дереве разбора выведена строка [math]vxy[/math]. Пусть [math]u[/math] и [math]z[/math] — строки, состоящие из терминалов, которые выведены соответственно из [math]\alpha[/math] и [math]\beta[/math] в данном дереве разбора. Тогда [math]S \Rightarrow^{*} uAz \Rightarrow^{*} uvAyz \Rightarrow^{*} \omega[/math].

Покажем, что [math]|vxy| \leqslant n[/math]. Допустим, что [math]|vxy|\gt n[/math]. Тогда высота поддерева с корнем в вершине, соответствующей выбранному [math]A[/math], не меньше [math]m+2[/math]. Рассмотрим поддерево вершины, в котором содержится нетерминал [math]A[/math]. Тогда высота этого поддерева не меньше [math]m+1[/math]. Рассмотрим путь максимальной длины от корня этого поддерева к листу. В нем содержится не менее [math]m+1[/math] нетерминалов, причем не содержится стартовый нетерминал. Следовательно, на этом пути найдутся два одинаковых нетерминала, что противоречит условию наибольшей удаленности от корня выбранного ранее нетерминала [math]A[/math]. Получили противоречие. Поэтому [math]|vxy|\leqslant n[/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]

Замечание. Условие леммы не является достаточным для контекстно-свободности языка. Но, в силу необходимости условия, данная лемма часто используется для доказательства неконтекстно-свободности языков.

Пример доказательства неконтекстно-свободности языка с использованием леммы

Рассмотрим язык [math]0^{n}1^{n}2^{n}[/math]. Покажем, что он не является контекстно-свободным.

Для фиксированного [math]n[/math] рассмотрим слово [math]\omega=0^n 1^n 2^n[/math]. Пусть [math]\omega[/math] разбили на [math]u, v, x, y, z[/math] произвольным образом. Так как [math]|vxy|\leqslant n[/math], то в слове [math]vxy[/math] не содержится либо ни одного символа [math]0[/math], либо ни одного символа [math]2[/math]. Для любого такого разбиения выбираем [math]k=2[/math] и получаем, что количество символов [math]1[/math] изменилось, а количество либо [math]0[/math], либо [math]2[/math] осталось тем же. Очевидно, что такое слово не принадлежит рассмотренному языку. Значит, язык [math]0^{n}1^{n}2^{n}[/math] не является контекстно-свободным по лемме о разрастании для КС-грамматик.

Пример не КС-языка, для которого выполняется лемма

Рассмотрю язык [math]L=\{a^{n}b^{n}c^{i}\mid i \neq n\}[/math].

Докажем, что он не контекстно-свободный. Для этого воспользуемся леммой Огдена. Для фиксированного [math]n[/math] рассмотрим слово [math]\omega=a^n b^n c^{n!+n}[/math]. Пометим все символы [math]a[/math] и [math]b[/math]. Пусть [math]\omega[/math] разбили на [math]u, v, x, y, z[/math], так что [math]x[/math] содержит выделенную позицию; [math]u[/math] и [math]v[/math] содержат выделенные позиции и [math]vxy[/math] содержат не более [math]n[/math] выделенных позиций. Тогда очевидно, что [math]vy[/math] должно содержать одинаковое число символов [math]a[/math] и [math]b[/math], иначе выбираем [math]k=0[/math] и тогда количество символов [math]a[/math] и [math]b[/math] станет разным. Пусть символов [math]a[/math] в [math]vy[/math] будет [math]t[/math]. Так же очевидно, что [math]vy[/math] не содержит символов [math]c[/math], так как [math]vxy[/math] содержат не более [math]n[/math] выделенных позиций, но [math]v[/math] точно содержит символ [math]a[/math]. Тогда выберем [math]k=\dfrac{n!}{t}+1[/math] и получим слово [math]a^{n!+n}b^{n!+n}c^{n!+n}[/math], которое не принадлежит рассмотренному языку. Значит [math]a^{n}b^{n}c^{i}[/math] не является контекстно-свободным.

Докажем, что язык удовлетворяет лемме о разрастании. Выберем [math]n=5[/math]. Это значит, что длина рассматриваемых слов не меньше [math]3[/math]. Рассмотрим случаи:

  1. [math]c^i[/math]
    Выберем [math]u=c^{i-1}[/math], [math]v=c[/math], [math]x=y=z=\varepsilon[/math].
  2. [math]a^jb^j[/math]
    Выберем [math]u=a^{j-1}[/math], [math]v=a[/math], [math]x=\varepsilon[/math], [math]y=b[/math], [math]z=b^{j-1}[/math].
  3. [math]a^jb^jc^i[/math], где [math]i \lt j-1[/math]
    Выберем [math]u=a^{j-1}[/math], [math]v=a[/math], [math]x=\varepsilon[/math], [math]y=b[/math], [math]z=b^{j-1}c^i[/math].
  4. [math]a^jb^jc^{j-1}[/math]
    Выберем [math]u=a^{j-2}[/math], [math]v=aa[/math], [math]x=\varepsilon[/math], [math]y=bb[/math], [math]z=b^{j-2}c^i[/math].
  5. [math]a^jb^jc^{j+1}[/math]
    Выберем [math]u=a^{j-2}[/math], [math]v=aa[/math], [math]x=\varepsilon[/math], [math]y=bb[/math], [math]z=b^{j-2}c^i[/math].
  6. [math]a^jb^jc^i[/math], где [math]i\gt j+1[/math]
    Выберем [math]u=a^jb^jc^{i-1}[/math], [math]v=c[/math], [math]x=y=z=\varepsilon[/math].

Таким образом язык [math]L[/math] не контекстно-свободный, но удовлетворяет второй части леммы.

См. также

Источники

  • Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)