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

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

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

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

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

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

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

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

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

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

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

См. также

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

Литература

• Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: «Вильямс», 2002. — С. 528. — ISBN 0-201-44124-1

• А.И.Белоусов, С.Б.Ткачев Дискретная математика / под ред. д.т.н. проф. В.С.Зарубина, д.ф.м.н. проф. А.П.Крищенко. — 4-е изд, испр.. — М.: изд-во МГТУ им.Н.Э.Баумана, 2006. — 744 с. — (математика в техническом университете). — 2000 экз. — ISBN 5-708-2886-4