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

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

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

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

$(\mathrm{\exists }n\in \mathbb{N})(\mathrm{\forall }\alpha \in L:|\alpha |>n)(\mathrm{\exists }u,x,v,y,w\in V^{*}):$
$\alpha =uxvyw\wedge |xy|>0\wedge |xvy|\le n\wedge (\mathrm{\forall }i\ge 0:u{x}^{i}v{y}^{i}w\in L).$.

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

См. также

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

Литература

• Шаблон:Книга

• Шаблон:Книга

• Шаблон:Книга