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

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

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

Пусть ${\displaystyle L}$ — контекстно-свободный язык над алфавитом V. Тогда

${\displaystyle (\exists n\in \mathbb {N} )(\forall \alpha \in L:|\alpha |>n)(\exists u,x,v,y,w\in V^{*}):}$
${\displaystyle \alpha =uxvyw\land |xy|>0\land |xvy|\leq n\land (\forall i\geq 0:ux^{i}vy^{i}w\in L).}$.

Иначе говоря, любую достаточно длинную строчку в ${\displaystyle L}$ можно разбить на пять частей так, что повторение второй и четвёртой частей произвольное количество раз (возможно, 0) не приведут к выходу за пределы языка.

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

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

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

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

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

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

См. также

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

Литература

• Кук Д., Вейз Г. Компьютерная математика / Пер, с англ. Г. М. Кобелькова. — М.: Наука, 1990. — 384 с. — ISBN 5-02 014216-6.

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

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