Изменения

Перейти к: навигация, поиск

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

6 байт добавлено, 23:00, 6 ноября 2016
м
опечатка
== Пример не КС-языка, для которого выполняется лемма ==
Рассмотрю язык <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 dpi=120>k=\fracdfrac{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> '''не''' контекстно-свободный, но удовлетворяет второй части леммы.
129
правок

Навигация