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

---

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

Если 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).}$.
Иначе говоря, любую достаточно длинную цепочку в КС-языке можно разбить на пять частей так, что повторение второй и четвёртой частей произвольное количество раз (возможно, 0) не приведут к выходу за пределы языка.

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

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

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

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

---