Изменения

Для фиксированного <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 (рус.) [[Категория: Теория формальных языков]][[Категория: Контекстно-свободные грамматики]][[Категория: Опровержение контекстно-свободности языка]]