Изменения
Нет описания правки
Таким образом, в рамках нашей грамматики мы можем построить цепочку вывода: <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>0</tex>, либо не одного символа <tex>2</tex>. Для любого такого разбиения выберем <tex>k=2</tex> и получаем, количество символов 1 изменилось, а количество либо <tex>0</tex>, либо <tex>2</tex> осталось тем же. Очевидно, что такое слово не принадлежит рассмотренному языку. Значит, язык <tex>0^{n}1^{n}2^{n}</tex> не является контекстно-свободным.
