Теорема Клини: регулярки = автоматы

Регулярное выражение и конечный автомат — два разных языка для описания одного и того же класс языков. Это и есть теорема Клини.

Теорема Клини: язык распознаётся конечным автоматом тогда и только тогда, когда он задаётся регулярным выражением. Эти классы совпадают.

Регулярные выражения формально

В теории регулярное выражение строится из трёх базовых операций над языками: объединение (записывается «|» или «+»), конкатенация (просто рядом) и звезда Клини (повтор 0+ раз, «*»). Базовые элементы: символ алфавита, ε (пустое слово), ∅ (пустой язык). Всё, что строится из них, — регулярное выражение, а его язык — регулярный язык. Например, (a|b)*abb — все строки над {a, b}, оканчивающиеся на «abb».

Это та самая теория за практическими regex из курса «Регулярные выражения». Учебные `\d`, `[a-z]+`, `^...$` — синтаксический сахар над этими тремя операциями. А вот «настоящие» возможности вроде обратных ссылок (`\1`) выходят за пределы регулярных языков — о чём ниже.

Две стороны теоремы

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

Регулярка → автомат (построение Томпсона). По структуре выражения собираем НКА-ε. Символ — два состояния и переход; конкатенация R·S — соединяем выход R с входом S ε-переходом; объединение R|S — новое стартовое состояние с ε-переходами в оба; звезда R* — ε-петля назад и ε-обход вперёд. Вот зачем нужны были ε-переходы из второго раздела — они и есть клей сборки.

R | S  (объединение):                R*  (звезда):

     ε  ┌─► [R] ─┐ ε                 ┌──── ε ────┐
  ──►(s)         (f)──►          ──►(s) ─► [R] ─►(f)──►
     ε  └─► [S] ─┘ ε                 └──── ε ◄───┘

Автомат → регулярка. Обратное направление — метод исключения состояний: по одному убираем состояния автомата, помечая рёбра регулярными выражениями, пока не останутся стартовое и финальное, соединённые единым regex'ом. Так доказывается, что любой ДКА выражается регуляркой.

Проверка регулярки симуляцией автомата

Раз regex эквивалентен автомату, мы можем «исполнить» простое выражение, построив ДКА вручную. Реализуем матчер для (ab)* — строк из повторов «ab».

# ДКА для (ab)* : q0 принимающее, ждём a; q1 ждём b; trap = мёртвое
delta = {
    ("q0","a"):"q1", ("q0","b"):"trap",
    ("q1","a"):"trap", ("q1","b"):"q0",
    ("trap","a"):"trap", ("trap","b"):"trap",
}
def matches_ab_star(w):
    st = "q0"
    for ch in w:
        st = delta[(st, ch)]
    return st == "q0"   # принимающее

for w in ["", "ab", "abab", "aba", "abb", "ba"]:
    print(f"{w or 'ε':>5} -> {matches_ab_star(w)}")

Вывод:

    ε -> True
   ab -> True
 abab -> True
  aba -> False
  abb -> False
   ba -> False

Пустая строка матчится ((ab)* допускает 0 повторов), «abab» матчится, «aba» — нет. Этот ДКА — буквальная компиляция регулярки (ab)*.

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

Промышленные regex-движки делятся на два лагеря. Автоматные (RE2 от Google, движок grep, awk) компилируют регулярку в НКА/ДКА и гарантируют линейное время O(n) от длины строки — потому что просто прогоняют автомат. Backtracking-движки (PCRE, движки в Python, Perl, JavaScript) поддерживают нерегулярные фичи (обратные ссылки), но платят за это: на патологических выражениях они уходят в экспоненциальное время (ReDoS-атаки). Теорема Клини объясняет, почему «честные» регулярные выражения всегда быстры, а расширения — нет.

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

Считать любые «regex» регулярными. Обратные ссылки (`(a+)\1`), рекурсивные шаблоны — НЕ регулярны, они выходят за класс регулярных языков. «Regex» в программировании ≠ «регулярное выражение» в теории.

Думать, что звезда — это «один или более». Звезда Клини — ноль или более; «один или более» — это «+», то есть R·R*.

Забывать ε в (ab)*. Пустая строка входит в язык любой звезды.

Итог

• Теорема Клини: регулярные выражения и конечные автоматы описывают один и тот же класс — регулярные языки.
• Регулярка → НКА-ε строится по Томпсону; автомат → регулярка — исключением состояний.
• Три операции регулярок: объединение, конкатенация, звезда Клини (0+ повторов).
• Обратные ссылки и рекурсия выходят за класс регулярных языков; автоматные движки за счёт этого работают за O(n).