Математическая теория формальных языков



         

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


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

длины не меньше p можно подобрать слова , для которых верно uvxyz = w,

(то есть или ),

и

для всех .

Доказательство. Пусть язык

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

Положим p = 2|N|. Пусть

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

Из того что G - грамматика в нормальной форме Хомского, заключаем, что . Неравенство

следует из того, что самый длинный путь в соответствующем слову vxy поддереве содержит не более |N| + 2 вершин. Для каждого

можно построить дерево вывода с кроной uvixyiz, комбинируя части исходного дерева вывода.

Пример 9.1.2.

Рассмотрим язык

над алфавитом {a,b,c}. Утверждение леммы 9.1.1 не выполняется ни для какого натурального числа p. Действительно, если uvxyz = apbpcp, |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, что множество




Содержание  Назад  Вперед