W5. Лемма о накачке для регулярных языков, автоматы с магазином (PDA)

Автор

Manuel Mazzara

Дата публикации

19 февраля 2026 г.

1. Краткое содержание

1.1 Почему некоторые языки не регулярны

Напомним: регулярный язык — это любой язык, который может быть распознан конечным автоматом (FSA). FSA — мощный инструмент, но у него принципиальное ограничение: есть лишь фиксированная конечная память — ровно текущее состояние. У FSA с состояниями можно «помнить» только то, в каком из этих состояний он находится, и не больше.

Из этого следует, что FSA не справляются с шаблонами, где нужно считать до произвольной глубины. Например:

  • : чтобы распознать этот язык, машина должна сосчитать символов a, а затем проверить ровно символов b. Сколько бы состояний ни было у FSA, при достаточно большом «памяти» не хватит.
  • : палиндромы чётной длины. Здесь нужно запомнить всю первую половину строки, а она может быть сколь угодно длинной.

Чтобы доказать регулярность языка, достаточно выписать работающий FSA. Чтобы доказать нерегулярность, задача сложнее: нужно показать, что ни один FSA язык не распознаёт. Перебрать все автоматы невозможно. Вместо этого используют лемму о накачке (Pumping Lemma).

1.2 Принцип Дирихле

Перед формулировкой леммы о накачке нужен классический принцип голубятни (Pigeonhole Principle):

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

pigeonhole p1 State q0 p2 State q1 p3 State q2 t1 visit 1 t1->p1 t2 visit 2 t2->p2 t3 visit 3 t3->p3 t4 visit 4 t4->p2 repeated state

Принцип Дирихле для автомата: визитов больше, чем состояний — значит, есть повтор состояния

Применение к FSA: состояния автомата — это «ящики», а переходы, пройденные при чтении строки, — «голуби». Если длина строки больше числа состояний , то при обработке автомат посещает больше состояний (с повторениями). Различных состояний только , значит какое-то состояние посещено дважды. Повторное состояние соответствует циклу в автомате.

1.3 У бесконечного регулярного языка обязан быть цикл

Пусть бесконечный регулярный язык распознаётся FSA с состояниями. Так как бесконечен, в нём есть строки сколь угодно большой длины. Когда FSA обрабатывает достаточно длинную строку (больше символов), он совершает больше переходов. По принципу Дирихле какое-то состояние повторяется.

pumping_loop start q0 q0 start->q0 q q q0->q x q->q y qf qf q->qf z

Длинный принимающий путь содержит петлю, которую можно накачивать

Тогда путь автомата выглядит так: где — строка, по которой мы «зациклились» в . Важно: так как машина детерминирована и возвращает в , по этому циклу можно пройти любое число раз: все ведут в то же принимающее состояние. Следовательно, все эти строки лежат в .

1.4 Лемма о накачке для регулярных языков
1.4.1 Формулировка

Лемма о накачке: если — регулярный язык, то существует целое (длина накачки / критическая длина) такое, что для любой строки с найдётся разбиение , для которого:

  1. (фрагмент накачки непуст)
  2. (накачка расположена в начале строки)
  3. для всех (сколько ни повторяй , строка остаётся в )

В качестве можно взять число состояний FSA, распознающего .

Набросок доказательства: пусть — FSA с , распознающий . Возьмём , . При чтении машина проходит не менее состояния (включая старт). По принципу голубятни какое-то повторяется. Пусть путь Первое повторение происходит не позже чем после прочтения не более символов с начала, откуда . Так как ведёт из в , имеем . Из следует, что накачка сколько угодно раз оставляет нас в , после чего ведёт в принимающее.

1.4.2 Необходимое, но не достаточное условие

Лемма о накачке даёт лишь необходимое условие регулярности, не достаточное:

  • регулярный для выполняется лемма (гарантированно)
  • Лемма выполняется регулярный (у некоторых нерегулярных языков лемма тоже «проходит»!)

Поэтому:

  • нельзя по лемме доказать регулярность;
  • можно доказать нерегулярность (через контрапозицию).
1.4.3 Контрапозиция: как доказывают нерегулярность

Контрапозиция леммы:

Если для любого существует с такая, что при любом разбиении с и найдётся с , то не регулярен.

Это и есть рабочий инструмент. Удобно думать как об игре в двух лиц:

Игрок 1 (противник) Игрок 2 (вы)
Задаёт любое Выбираете с
Задаёт любое разбиение с и Находите , что

Вы выигрываете (язык не регулярен), если всегда можете ответить, как бы ни действовал противник.

1.4.4 Стандартный шаблон доказательства
  1. Предположим от противного, что регулярен.
  2. Пусть — длина накачки из леммы.
  3. Выберите слово , (тактически так, чтобы любое допустимое разбиение «ломало» язык).
  4. Рассмотрите произвольное допустимое , , .
  5. Используйте , чтобы ограничить положение .
  6. Найдите , что .
  7. Вывод: лемма нарушена — не регулярен.

Самый творческий шаг — выбор . Удачный выбор заставляет состоять из одного типа символов, и накачка легко разрушает структуру языка.

1.4.5 Классический пример:

Утверждение: не регулярен.

Доказательство:

  1. Пусть регулярен, — длина накачки.
  2. Возьмём , .
  3. Любое , , .
  4. Первые символов — все a, значит целиком в блоке a: , , , .
  5. Тогда .
  6. При : .
  7. Так как , число a больше , а b ровно , значит .

Противоречие с леммой.

Три случая из лекции: можно разобрать все разбиения без опоры только на :

  • Случай 1: — накачка даёт
  • Случай 2: —
  • Случай 3: (смешанный) —
1.5 Автоматы с магазином (PDA)
1.5.1 Мотивация: за пределами регулярных языков

Лемма о накачке показывает, что для FSA не хватает памяти для «счёта». Нужна модель с большей памятью — естественно добавить стек к FSA, получив автомат с магазином (Pushdown Automaton, PDA).

Иерархия (от слабой к сильной):

  • Комбинационная логика (без памяти)
  • FSA (конечная память — только состояние)
  • PDA (неограниченный стек — контекстно-свободные языки, CFL)
  • Машина Тьюринга (лента — всё вычислимое)

PDA ровно на ступень выше FSA; они распознают контекстно-свободные языки, включая вложенные скобки, баланс и т.п.

1.5.2 Что такое стек?

Стек — структура «последним пришёл — первым ушёл» (LIFO), как стопка тарелок: добавлять и снимать можно только сверху.

stack_ops top top: c mid b top->mid pop pop top->pop low a mid->low z0 Z₀ low->z0 push push push->top

Стек: push кладёт наверх, pop снимает последний символ

  • Push: положить символ наверх.
  • Pop: снять верхний (и «прочитать» его).

На дне стека обычно специальный маркер ; по нему проверяют «пустоту» (остался только ).

Пример — push , , :

Из пустого стека (только ):

  1. После push : сверху вниз
  2. После push :
  3. После push :
  4. После pop: сняли ; осталось

Последний положенный символ снимается первым — свойство LIFO.

Историческая заметка: идею стека ввёл Алан Тьюринг в работе 1946 г. об ACE; операции называл BURY и UNBURY в теории подпрограмм.

1.5.3 Неформальное описание

У FSA есть входная лента и конечное управление (состояние).

PDA то же самое, плюс стек:

  • Управление читает следующий символ входа и вершину стека.
  • По ним (и по состоянию) переходит в новое состояние и заменяет вершину стека строкой символов.

pda_arch input Input Tape control q input->control read a or ε next q' control->next transition stack Stack A A Z₀ stack->control top symbol next->stack replace top

PDA: конечное управление читает вход и вершину стека, затем обновляет оба

PDA может:

  • Push: поместить символ(ы) в стек (заменить вершину на более длинную строку)
  • Pop: извлечь символ из стека (заменить вершину на )
  • Не менять стек (заменить символ самим собой)
  • Делать -переходы (не двигать головку по входу, только стек)
1.5.4 Формальное определение

PDA — кортеж из 7 компонент:

где:

  • — конечное множество состояний
  • — конечный входной алфавит
  • — конечный алфавит магазина
  • — функция переходов
  • — начальное состояние
  • — начальный символ стека
  • — принимающие (финальные) состояния

Чтение перехода: значит: > В , прочитав из входа (или ), при наверху стека: перейти в и заменить на строку .

На стрелках пишут : «прочитать , снять , положить ».

  • Push под :
  • Pop :
  • Без изменений:
1.5.5 Шаги PDA

За шаг определяют:

  1. Текущее состояние
  2. Текущий входной символ (или )
  3. Вершина стека

За один шаг PDA одновременно:

  • меняет состояние на
  • двигает головку по входу (или не двигает при )
  • заменяет вершину на

Так как даёт множество исходов, в общем виде PDA недетерминированы. (PDA детерминирован (DPDA), если и из следует .)

1.5.6 Условия принятия
  • По финальному состоянию: вход исчерпан и PDA в ; содержимое стека не важно.
  • По пустому стеку: вход исчерпан и стек «пуст» (только или пусто); состояние не важно.

Для недетерминированных PDA оба режима эквивалентны. Для DPDA — не эквивалентны.

Замечание: при приёме по пустому стеку язык должен быть префикс-свободным (ни одна строка языка не является собственным префиксом другой): после опустошения стека продолжить чтение нельзя.

1.5.7 Пошаговый пример: PDA для

Идея: по одному a кладём , по одному b снимаем . Если после всех b стек ровно «пуст» по смыслу задачи, длины совпали.

Состояния: (старт), (читаем a), (читаем b), (принятие).

.

Переходы:

  • :
  • :
  • :
  • :
  • :

Трассировка для aabb:

Шаг Состояние Остаток входа Стек (сверху) Переход
1 :
2 :
3 :
4 :
5 :
6 ПРИНЯТО

2. Определения

  • Регулярный язык: , для которого существует FSA с .
  • Лемма о накачке: для регулярного существует : любое , , раскладывается с , и .
  • Длина накачки (): можно взять число состояний распознающего FSA.
  • Накачка: повторение средней части в ; раз даёт .
  • Контрапозиция леммы: если , , что для всех допустимых разбиений найдётся с , то не регулярен.
  • Принцип Дирихле: объектов, контейнеров — в каком-то контейнере больше одного объекта.
  • Цикл в FSA: путь, начинающийся и заканчивающийся в одном состоянии.
  • PDA: модель с конечным управлением, входной лентой и стеком; формально 7-кортеж . Распознают ровно CFL.
  • Стек: LIFO; операции push и pop.
  • Алфавит стека (): конечный; обычно включает .
  • Символ дна стека (): маркер дна.
  • PDA: ; переход — прочитать , заменить на .
  • -переход: без чтения входа.
  • Принятие по финальному состоянию: вход исчерпан, состояние .
  • Принятие по пустому стеку: вход исчерпан, стек пуст (в смысле определения); для NPDA эквивалентно финальному состоянию.
  • Контекстно-свободный язык (CFL): язык, распознаваемый PDA; эквивалентно порождён КС-грамматикой. Всякий регулярный — CFL, обратное неверно.
  • NPDA: у может быть несколько исходов; принятие, если существует успешная ветка.
  • DPDA: автомат с магазином, у которого на каждом шаге не более одного возможного перехода: для всех ; кроме того, если , то (нельзя одновременно читать символ с входа и делать -переход с той же вершиной стека).

3. Формулы

  • Лемма (регулярные): : , , , , ,
  • Контрапозиция: не регулярен, если , , допустимых
  • Длина после накачки:
  • Ограничение на : вынуждает лежать в первых символах
  • Нотация переходов PDA: ; для тихого шага:
  • Формально PDA: ,
  • Принятие по финальному состоянию: принимается для некоторого ,

4. Примеры

4.1. Доказать, что не регулярен (Лаба 5, Задание 1)

Докажите леммой о накачке, что над не регулярен.

(Здесь — обращение строки ; — все палиндромы чётной длины над .)

Показать решение

Идея: всегда палиндром. Возьмём ; накачка в левом блоке a даёт непалиндром.

  1. Пусть регулярен, — длина накачки.
  2. (, ), .
  3. Произвольное , , .
  4. Первые символов — a, значит из a: , , , .
  5. : .
  6. Символ на позиции слева — первый b в блоке; справа от конца — всё ещё a при . Не палиндром .
  7. Вывод: не регулярен.

Ответ: не регулярен.

4.2. Доказать, что не регулярен (Лаба 5, Задание 2)

Докажите леммой о накачке, что не регулярен.

Показать решение

Идея: любая строка из содержит поровну символов a и b. Слово вынуждает лежать в блоке a; накачка вниз убирает часть a, не трогая b, и баланс нарушается.

  1. Предположим от противного, что регулярен. Пусть — длина накачки.
  2. Возьмём . Тогда .
  3. Рассмотрим произвольное с и .
  4. Так как первые символов — все a и , целиком в блоке a: , , .
  5. Возьмём :
  6. Тогда , . При имеем , счётчики не равны, значит .
  7. Противоречие с леммой. не регулярен.

Ответ: не регулярен.

4.3. Доказать, что не регулярен (Лаба 5, Задание 3)

Докажите леммой о накачке, что над не регулярен.

Показать решение

Идея: факториалы растут быстрее любой линейной прибавки от накачки. Для соседних факториалов гораздо больше при больших . Любая накачка с не «перепрыгнет» зазор от к , и некоторая накачанная строка окажется строго между двумя последовательными факториалами.

  1. Пусть регулярен, — длина накачки.

  2. , при .

  3. Произвольное , , .

  4. Положим , тогда .

  5. Возьмём :

  6. Нижняя граница: . Верхняя граница: . До следующего факториала: . Нужно , т.е. . При из следует . Значит , длина не равна ни одному , и .

    (При единственное ; возьмём : , а , так как для .)

  7. Лемма нарушена, не регулярен.

Ответ: не регулярен.

4.4. Доказать, что не регулярен (Лаба 5, Задание 4)
Показать решение

Идея: в число символов c равно сумме чисел a и b. Слово заставляет лежать в блоке a; накачка вниз уменьшает число a, не трогая b и c, и равенство для c нарушается.

  1. Пусть регулярен, — длина накачки.
  2. (, тогда ), .
  3. Произвольное , , .
  4. Первые символов — a, значит , , .
  5. : .
  6. Для членства в нужно , но фактически , при не совпадает. Значит .
  7. не регулярен.

Ответ: не регулярен.

4.5. Доказать, что не регулярен (Туториал 5, Пример 1)
Показать решение

Идея: ; ограничение вынуждает лежать в блоке a; любая накачка нарушает равенство чисел a и b.

  1. Пусть регулярен, — длина накачки.
  2. , .
  3. Произвольное , , .
  4. целиком из a: , , , , .
  5. : .
  6. При число a не равно числу b, значит .
  7. не регулярен.

Дополнение — три случая без : (a) — ; (b) — ; (c) — после накачки в середине появляется b перед a, не формат .

Ответ: не регулярен.

4.6. Доказать, что не регулярен (Туториал 5, Пример 2)
Показать решение

Идея: слово ; единственный b в центре — «ориентир»: в ровно один b и поровну a слева и справа. Накачка левого блока a ломает симметрию.

  1. Пусть регулярен, — длина накачки.
  2. , .
  3. Произвольное , , .
  4. Так как и первые символов — все a, целиком в левом блоке a: , , , , где .
  5. При :
  6. Для членства в нужно равенство длин левого и правого блоков a, то есть , что невозможно при . Значит .
  7. Лемма нарушена, не регулярен.

Ответ: не регулярен.

4.7. PDA для (Туториал 5, Пример 3)
Показать решение

pda_abn_w5 start p0 p0 start->p0 p1 p1 p0->p1 a, Z₀/AZ₀ p1->p1 a, A/AA p2 p2 p1->p2 b, A/ε p2->p2 b, A/ε p3 p3 p2->p3 ε, Z₀/Z₀

PDA для aⁿbⁿ

  1. PDA: состояния (принимающее), .

  2. Переходы:

    Переход Смысл
    : Первый a: положить
    : Каждый следующий a: ещё
    : Первый b: снять
    : Каждый следующий b: снять
    : Конец входа, наверху — принять

  3. Трассировка aabb: как в табл. разд. 1.5.7 — принято.

  4. Корректность: на кладётся и снимается по символов ; при либо остаются , либо до нельзя дойти честно.

Ответ: указанный PDA распознаёт .

4.8. PDA для (Туториал 5, Пример 4)
Показать решение

pda_aba start q0 q0 start->q0 q0->q0 a, Z₀/AZ₀ a, A/AA q1 q1 q0->q1 b, A/A q1->q1 a, A/ε q2 q2 q1->q2 ε, Z₀/Z₀

PDA для aⁿbaⁿ

  1. PDA: (левые a), (после единственного b, правые a), (принимающее); .

  2. Переходы:

    Переход Смысл
    : Первый a слева
    : Следующие a слева
    : Видим b, не снимая , переходим к правой части
    : Каждый a справа снимает
    : Все сняты, наверху — принять

  3. Трассировка aba: ; ; ; — принято.

  4. aabaa: аналогично, два push слева, два pop справа — принято.

Ответ: указанный PDA распознаёт .