748
правок
Изменения
→Пример доказательства неконтекстно-свободности языка с использованием леммы
Для фиксированного <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>a^{n}b^{n}c^{i}</tex>, где <tex>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=\frac{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>
== См. также ==
