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

Лемма 9.1.1 (pumping lemma, лемма о разрастании, лемма о накачке, лемма-насос) Пусть L - контекстно-свободный язык над алфавитом . Тогда найдется такое положительное целое число p, что для любого слова длины не меньше p можно подобрать слова , для которых верно uvxyz = w, (то есть или ), и для всех .

Доказательство. Пусть язык порождается грамматикой в нормальной форме Хомского . Индукцией по k легко доказать, что для любого дерева вывода в грамматике G длина кроны дерева не превышает 2^k-2, где k - количество вершин в самом длинном пути, начинающемся в корне дерева и заканчивающемся в некоторой вершине, помеченной символом из .

Положим p = 2^|N|. Пусть и . Зафиксируем некоторое дерево вывода с кроной w в грамматике G. Рассмотрим самый длинный путь в этом дереве. Этот путь содержит не менее |N| + 2 вершин. Среди них найдутся две вершины с одинаковыми метками, причем их можно выбрать среди последних |N| + 2 вершин рассматриваемого пути. Выберем слова u, v, x, y и z так, что uvxyz = w, поддерево с корнем в одной из найденных вершин имеет крону xи поддерево с корнем в другой найденной вершине имеет крону vxy.

Из того что G - грамматика в нормальной форме Хомского, заключаем, что . Неравенство следует из того, что самый длинный путь в соответствующем слову vxy поддереве содержит не более |N| + 2 вершин. Для каждого можно построить дерево вывода с кроной uvⁱxyⁱz, комбинируя части исходного дерева вывода.

Пример 9.1.2. Рассмотрим язык над алфавитом {a,b,c}. Утверждение леммы 9.1.1 не выполняется ни для какого натурального числа p. Действительно, если uvxyz = a^pb^pc^p, |vy| > 0 и , то |vy|_a = 0 или |vy|_c = 0. Следовательно, |uvvxyyz|_a = p или |uvvxyyz|_c = p. Так как |uvvxyyz| > 3p, то . Из этого можно заключить, что язык L не является контекстно-свободным.

Теорема 9.1.3. Каждый контекстно-свободный язык над однобуквенным алфавитом является автоматным.

Доказательство. Пусть дан контекстно-свободный язык L над алфавитом {a}. Согласно лемме 9.1.1 найдется такое натуральное число p, что множество является объединением некоторого семейства арифметических прогрессий, причем у каждой прогрессии первый член и шаг не больше числа p. Так как существует лишь конечное число прогрессий натуральных чисел с таким ограничением, рассматриваемое семейство конечно. Следовательно, язык L является автоматным (используем пример 2.1.18).

Упражнение 9.1.4. Является ли контекстно-свободным язык ?

Упражнение 9.1.5. Является ли контекстно-свободным язык ?

Упражнение 9.1.6. Является ли контекстно-свободным язык ?

Упражнение 9.1.7. Является ли контекстно-свободным язык {a^m | m простое}?

Упражнение 9.1.8. Является ли контекстно-свободным язык ?

Упражнение 9.1.9. Является ли контекстно-свободным язык ?

Упражнение 9.1.10. Является ли контекстно-свободным язык ?

Упражнение 9.1.11. Является ли контекстно-свободным язык ?

Упражнение 9.1.12. Является ли контекстно-свободным язык ?

Упражнение 9.1.13. Является ли контекстно-свободным язык {a^kb^mcⁿ | k < max(m,n)}?

Упражнение 9.1.14. Является ли контекстно-свободным язык {a^kb^mcⁿ | k > max(m,n)}?

Упражнение 9.1.15. Является ли контекстно-свободным язык

Упражнение 9.1.16. Какому классу принадлежит язык, порождаемый грамматикой

Упражнение 9.1.17. Существуют ли такие контекстно-свободные языки и , что язык не является контекстно-свободным?

9.2*. Лемма о разрастании для линейных языков

Определение 9.2.1. Линейная грамматика в нормальной форме - это такая линейная грамматика, в которой каждое правило имеет вид , , или , где , , .

Теорема 9.2.2. Каждая линейная грамматика эквивалентна некоторой линейной грамматике в нормальной форме.

Теорема 9.2.3. Если линейный язык не содержит пустого слова, то он порождается некоторой линейной грамматикой в нормальной форме без - правил.

Теорема 9.2.4. Язык L является линейным тогда и только тогда, когда язык является линейным.

Лемма 9.2.5. Пусть L - линейный язык над алфавитом . Тогда найдется такое положительное целое число p, что для любого слова длины не меньше p можно подобрать слова , для которых верно uvxyz = w, (то есть или ), и для всех .

Доказательство. Пусть язык порождается линейной грамматикой в нормальной форме без -правил. Положим p = |N| + 1. Пусть и . Зафиксируем некоторое дерево вывода слова w в грамматике G. Рассмотрим самый длинный путь в этом дереве (он начинается с корня и заканчивается некоторым листом, помеченным символом из ). Этот путь содержит не менее |N| + 1 вершин, помеченных элементами N. Среди первых |N| + 1 вершин рассматриваемого пути найдутся две вершины с одинаковыми метками. Выберем слова u, v, x, y и z так, что uvxyz = w, поддерево с корнем в одной из найденных вершин имеет крону x и поддерево с корнем в другой найденной вершине имеет крону vxy.

Пример 9.2.6. Рассмотрим язык над алфавитом {a,b}. Утверждение леммы 9.2.5 не выполняется ни для какого натурального числа p. Следовательно, язык L не является линейным.