Лемма о разрастании для контекстно-свободных языков

Лемма о разрастании для контекстно-свободных языков — лемма, по аналогии с одноименной леммой для регулярных языков позволяющая относительно несложно доказывать, что данный язык не является контекстно-свободным.

Формулировка

Если L — КС-язык над алфавитом V, то
$(\exists n\in \mathbb {N} )(\forall \alpha \in L:|\alpha |>n)(\exists u,x,v,y,w\in V^{*}):$
$\alpha =uxvyw\land |xy|>0\land |xvy|\leq n\land (\forall i\geq 0:ux^{i}vy^{i}w\in L).$.
Иначе говоря, любую достаточно длинную цепочку в КС-языке можно разбить на пять частей так, что повторение второй и четвёртой частей произвольное количество раз (возможно, 0) не приведут к выходу за пределы языка.

Доказательство

Пусть задан КС-язык (V, N, S, G), причем грамматика языка приведена (то есть не содержит правил вида A → ε или A → B).

Поскольку количество нетерминальных символов конечно, равно как и длина каждого правила вывода, то длина цепочки, высота дерева вывода для которой не превышает |N|, также ограничена сверху неким числом n.

Рассмотрим цепочку $\alpha :|\alpha |>n$. В силу вышесказанного высота дерева её вывода превысит |N|, то есть найдется путь из аксиомы в один из терминальных символов, длина которого будет больше, чем количество нетерминальных символов грамматики. Поскольку на каждом шаге заменяется один нетерминальный символ, как минимум один нетерминальный символ Q на этом пути будет заменён дважды. Из этого следует, что существует цепочка xQy с непустыми x или y, выводящаяся из Q. Следовательно, в процессе вывода S →* α процесс вывода Q →* xQy можно повторять сколь угодно много раз или опустить.

Тривиальное следствие: в любом бесконечном КС-языке найдется бесконечное подмножество цепочек, длины которых образуют возрастающую арифметическую прогрессию.

Примеры использования

• Язык $a^{n}b^{n}c^{n},n\geq 0$ не является КС-языком: в нём невозможно выбрать две цепочки и накачивать их, не выходя за пределы языка (необходимо одновременно накачивать три цепочки).
• Язык $a^{n}b^{n}c^{k},n,k\geq 0,k\leq n$ также не является КС-языком, но доказать это «накачиванием» уже не получится: можно накачивать «зоны» символов a и b, воспользовавшись тем, что символов c в цепочке может быть меньше. Но если рассмотреть принадлежащую языку цепочку $a^{n}b^{n}c^{n}$, то или исключение накачиваемых цепочек выведет за пределы языка, что противоречит лемме о накачке.
• Язык $a^{n^{2}}$ также не является КС-языком, так как он противоречит следствию из леммы.

См. также

• Лемма о накачке для регулярных языков
• Контекстно-свободная грамматика

Литература

• Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: «Вильямс», 2002. — С. 528. — ISBN 0-201-44124-1.
• А.И.Белоусов, С.Б.Ткачев. Дискретная математика / под ред. д.т.н. проф. В.С.Зарубина, д.ф.м.н. проф. А.П.Крищенко. — 4-е изд, испр.. — М.: изд-во МГТУ им.Н.Э.Баумана, 2006. — 744 с. — (математика в техническом университете). — 2000 экз. — ISBN 5-708-2886-4.