editor
177
правок
Изменения
м
Нет описания правки
}}
'''Замечание.''' Условие леммы не является достаточным для контекстно-свободности языка. Но в силу необходимости , данная лемма часто используется для доказательства того, что язык не является контекстнонеконтекстно-свободным свободности языков.
=== Пример доказательства неконтекстно-свободности языка с использованием леммы ===
Рассмотрим язык <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> не является контекстно-свободным.
