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

Как доказать, что язык НЕ регулярный? Главный инструмент — лемма о накачке: у длинных строк регулярного языка есть повторяющийся участок, который можно «качать».

Лемма о накачке: для любого регулярного языка L существует число p (длина накачки) такое, что любую строку s ∈ L длиной ≥ p можно разбить s = xyz, где |y| > 0, |xy| ≤ p, и xyⁱz ∈ L для всех i ≥ 0.

Откуда берётся накачка

Интуиция проста и опирается на конечность ДКА. Пусть L распознаётся ДКА с p состояниями. Возьмём строку длиной ≥ p. Читая её, автомат проходит ≥ p+1 состояний (считая стартовое). Состояний всего p, значит по принципу Дирихле (принципу ящиков) какое-то состояние повторится! Между двумя визитами в это состояние автомат прочитал непустой кусок y — он образует цикл в диаграмме. А раз есть цикл, по нему можно пройти 0 раз (выкинуть y), 1 раз (исходная строка), 2 раза, 10 раз — и автомат всё равно окажется в том же состоянии. Значит все строки xyⁱz тоже принимаются.

строка длиной ≥ p проходит цикл по повторённому состоянию q:

  q0 --x--> (q) --y--> (q) --z--> принимающее
               └──┘
             цикл y можно повторять: xz, xyz, xyyz, ... ∈ L

Как доказывают НЕ-регулярность

Лемма — необходимое условие регулярности. Поэтому её используют «от противного»: предположим, что L регулярен. Тогда по лемме есть p. Мы как «противник» выбираем конкретную хитрую строку s ∈ L длиной ≥ p. Лемма обещает разбиение s = xyz с |xy| ≤ p и |y| > 0. Мы показываем, что при любом таком разбиении найдётся i, для которого xyⁱz ∉ L. Противоречие — значит L не регулярен.

Классика: L = {aⁿbⁿ | n ≥ 0} не регулярен. Берём s = a^pb^p. Условие |xy| ≤ p означает, что x и y состоят только из символов a (первые p символов — это все a). Значит y = a^k, k > 0. Накачаем i = 2: xy²z = a^p+kb^p. Теперь a больше, чем b — строки нет в L. Противоречие. L не регулярен. Конечная память ДКА не может «сосчитать» n.

Демонстрация: цикл реально качается

Покажем механику накачки программно. Возьмём регулярный язык ab*c (a, потом сколько-то b, потом c) — у него y = «b» в цикле, и накачка остаётся в языке. А для aⁿbⁿ накачка вылетает.

import re
regular = re.compile(r"^ab*c$")     # регулярный язык

# s = abc, разбиение x='a', y='b', z='c'
x, y, z = "a", "b", "c"
for i in range(4):
    s = x + y*i + z
    print(f"i={i}: {s:>6} в языке ab*c? {bool(regular.match(s))}")

print("---")
# а вот a^n b^n: накачка ломает баланс
def is_anbn(s):
    n = len(s) // 2
    return s == "a"*n + "b"*n and len(s) % 2 == 0

x, y, z = "aa", "a", "bbb"   # s=aaabbb, y из зоны a
for i in range(3):
    s = x + y*i + z
    print(f"i={i}: {s:>7} в a^n b^n? {is_anbn(s)}")

Вывод:

i=0:     ac в языке ab*c? True
i=1:    abc в языке ab*c? True
i=2:   abbc в языке ab*c? True
i=3:  abbbc в языке ab*c? True
---
i=0:   aabbb в a^n b^n? False
i=1:  aaabbb в a^n b^n? True
i=2: aaaabbb в a^n b^n? False

В регулярном ab*c накачка любого i остаётся в языке. В aⁿbⁿ уже i=0 (и i=2) выбрасывают строку наружу — наглядное противоречие с леммой.

Как работает под капотом

Глубинная причина — принцип Дирихле плюс конечность состояний. Любой автомат с p состояниями на строке длиннее p обязан зациклиться. Лемма — формализация этого факта. Заметьте: лемма даёт необходимое, но не достаточное условие — есть нерегулярные языки, проходящие лемму. Для них применяют усиленные инструменты (лемма Майхилла-Нероуда). Но для большинства учебных задач «накачать и сломать» — рабочий метод.

Частые ошибки

Выбирать разбиение за лемму. Разбиение xyz выбирает «противник» (лемма), а вы должны сломать все допустимые разбиения. Зато строку s выбираете вы — берите самую неудобную.

Забыть условие |xy| ≤ p. Именно оно фиксирует, что y попадает в начальную зону (в aⁿbⁿ — в зону a). Без него доказательство разваливается.

Думать, что лемма доказывает регулярность. Нет, только не-регулярность. Прохождение леммы не гарантирует регулярность.

Итог

• Лемма о накачке: у регулярного языка есть p, и длинные строки разбиваются s = xyz с накачиваемым y (|y| > 0, |xy| ≤ p).
• Причина — повтор состояния (принцип Дирихле) образует цикл, который можно проходить любое число раз.
• Не-регулярность доказывают от противного: выбираем хитрую s и ломаем все разбиения накачкой.
• Пример: aⁿbⁿ не регулярен — конечная память не считает n; лемма — необходимое, но не достаточное условие.