Лемма о разрастании для контекстно-свободных языков (-теорема) — аналог леммы о разрастании для регулярных языков, позволяющий относительно несложно доказывать, что данный язык не порождается контекстно-свободной грамматикой: для контекстно-свободного языка над алфавитом выполнено: . Иначе говоря, любую достаточно длинную строчку в можно разбить на пять частей так, что повторение второй и четвёртой частей произвольное количество раз (возможно, 0) не приведут к выходу за пределы языка.
Естественное следствие результата состоит в том, что в любом бесконечном контекстно-языке найдётся бесконечное подмножество цепочек, длины которых образуют возрастающую арифметическую прогрессию.
Примеры Язык не является контекстно-свободным языком: в нём невозможно выбрать две цепочки и накачивать их, не выходя за пределы языка (необходимо одновременно накачивать три цепочки).
Язык также не является контекстно-свободным языком, но доказать это «накачиванием» уже не получится: можно накачивать «зоны» символов и , воспользовавшись тем, что символов в цепочке может быть меньше; однако цепочка выведет за пределы языка, что противоречит лемме о разрастании.
Язык также не является контекстно-свободным языком, так как он противоречит следствию из леммы.
Литература
Категория:Формальные языки Р