Изменения
Нет описания правки
Выберем <tex>n=2^{m+1}</tex>. Построим дерево разбора произвольного слова <tex>\omega</tex> длиной больше, чем <tex>n</tex>. Высотой дерева разбора назовем максимальное число нетерминальных символов на пути от корня дерева к листу. Так как грамматика языка <tex>L</tex> записана в НФХ, то у любого нетерминала в дереве могут быть, либо два потомка нетерминала, либо один потомок терминал. Поэтому высота дерева разбора слова <tex>\omega</tex> не меньше <tex>m+1</tex>.
Выберем путь от корня дерева к листу максимальной длины. Количество нетерминалов в нем не меньше, чем <tex>m+1</tex>, следовательно, найдется такой нетерминал <tex>B</tex>, который встречается на этом пути дважды. Значит, в дереве разбора найдется нетерминал <tex>B</tex>, в поддереве которого содержится нетерминал <tex>B</tex>. Выберем нетерминал <tex>A</tex>, у которого в поддереве содержится такой же нетерминал и длина пути до корня максимальна среди всех нетерминалов, содержащих в поддереве такой же нетерминал.
Найдем слова <tex> u,v,x,y,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> не является контекстно-свободным.
==Источники==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
