Автоматы, формальные языки и грамматики

Есть задача, которую вы решаете почти каждый рабочий день, даже если никогда не называли её так: проверить, принадлежит ли строка некоторому множеству допустимых строк, и заодно понять её структуру. Валиден ли этот email. Является ли это корректным JSON. Разобрать лог-строку. Понять, что x = a + b * c — это присваивание, а не мусор. Отловить сигнатуру атаки в сетевом трафике. Проверить, что последовательность вызовов API соответствует протоколу.

Теория формальных языков — это математика, которая отвечает на два вопроса про такие задачи:

1. Какой минимум памяти нужен, чтобы распознать данное множество строк? Ответ разбивает все языки на строгую иерархию: константная память (конечный автомат), стек (МП-автомат), линейная память, неограниченная лента (машина Тьюринга).
2. Какую цену вы платите за выразительность? Регулярное выражение проверяется за O(n) в один проход и с фиксированной памятью. Контекстно-свободная грамматика — уже O(n^3) в общем случае. За пределами — начинается неразрешимость.

Это не абстракция: именно из этой теории следует, почему grep в Go никогда не зависает, а grep c PCRE может повесить прод; почему регулярным выражением нельзя распарсить HTML; почему yacc ругается на «shift/reduce conflict»; и почему валидатор вложенных скобок в конфиге нельзя написать регуляркой, а можно счётчиком.

Статья опирается на Теорию множеств (языки — это множества слов) и Теорию графов (автомат — это помеченный орграф), а естественным продолжением служат Теория вычислимости и Теория сложности.

Алфавит, слово, язык: базовые определения

Начнём педантично — здесь важна каждая деталь, потому что дальше на этих определениях держатся доказательства.

Определение (алфавит). Алфавит Σ — конечное непустое множество символов. Например Σ = {0, 1}, Σ = {a, b}, Σ = ASCII, Σ = множество типов токенов.

Определение (слово). Слово (строка) над Σ — конечная последовательность символов из Σ. Пустое слово обозначается ε (длина 0). Длина слова w — |w|.

Определение (Σ*). Σ* — множество всех слов над Σ, включая ε. Σ+ = Σ* \ {ε}. Множество Σ* счётно бесконечно даже для однобуквенного алфавита.

Определение (язык). Язык L над Σ — произвольное подмножество Σ*, то есть L ⊆ Σ*.

Последнее определение выглядит невинно, но из него сразу следует фундаментальный факт. Множество всех языков над Σ — это P(Σ*), булеан счётного множества, а он несчётен (диагональ Кантора, см. Теорию множеств). Множество всех программ — счётно. Значит, почти все языки не описываются никакой программой. Всё, чем мы занимаемся ниже, — это исследование крошечного счётного островка «описуемых» языков внутри несчётного океана.

Σ* — это свободный моноид

Σ* с операцией конкатенации и нейтральным элементом ε образует моноид: конкатенация ассоциативна, εw = wε = w. Более того, это свободный моноид, порождённый Σ — в нём нет никаких соотношений, кроме вынужденных аксиомами.

Это не украшение, а рабочий инструмент. Свободность означает универсальное свойство: любое отображение f: Σ -> M в произвольный моноид M единственным образом продолжается до гомоморфизма f*: Σ* -> M. По-инженерному — любой fold по строке с ассоциативной операцией задаётся тем, что вы делаете с одним символом. Именно поэтому подсчёт хешей, подсчёт баланса скобок и, как мы увидим, работа конечного автомата параллелизуются и разбиваются на куски. Подробнее — в статье про абстрактную алгебру.

Операции над языками

Объединение:      L1 ∪ L2 = { w : w ∈ L1 или w ∈ L2 }
Пересечение:      L1 ∩ L2 = { w : w ∈ L1 и w ∈ L2 }
Дополнение:       ~L      = Σ* \ L
Конкатенация:     L1 · L2 = { uv : u ∈ L1, v ∈ L2 }
Степень:          L^0 = {ε},  L^(k+1) = L^k · L
Звезда Клини:     L*  = объединение L^k по всем k >= 0        (всегда содержит ε)
Плюс:             L+  = объединение L^k по всем k >= 1
Обращение:        L^R = { w перевёрнутое : w ∈ L }

Две ловушки, на которых спотыкаются: {} (пустой язык) и {ε} (язык из одного пустого слова) — это разные языки. {}* = {ε}, а {} · L = {} для любого L. В регулярках эта разница проявляется как разница между «не совпало ничего» и «совпало пустое совпадение» — источник бесконечных циклов в наивных реализациях findall.

Детерминированный конечный автомат (DFA)

Определение. DFA — пятёрка M = (Q, Σ, δ, q0, F), где:

• Q — конечное множество состояний;
• Σ — алфавит;
• δ: Q × Σ -> Q — функция переходов (всюду определённая, тотальная);
• q0 ∈ Q — начальное состояние;
• F ⊆ Q — множество принимающих состояний.

Расширим δ на слова: δ*(q, ε) = q, δ*(q, wa) = δ(δ*(q, w), a). Тогда

L(M) = { w ∈ Σ* : δ*(q0, w) ∈ F }

Интуиция «на пальцах»: автомат читает вход слева направо, ровно один раз, без возвратов, и вся его память — это номер текущего состояния. Он не может ничего «запомнить» сверх того, что уместилось в конечное число состояний. Не может посчитать, сколько было открывающих скобок, если их может быть сколько угодно. Не может сравнить первую половину слова со второй. Зато он работает за O(n) времени и O(1) дополнительной памяти — характеристики, которые не бьёт ничто.

Пример руками: числа, кратные 3

Возьмём Σ = {0, 1}, вход — двоичная запись числа старшим битом вперёд. Хотим принять слова, обозначающие числа, кратные 3. Ключевое наблюдение: если прочитанный префикс равен v, то после чтения бита b значение становится 2v + b. Нам не нужно значение — нужен только остаток по модулю 3:

новый_остаток = (2 * старый_остаток + b) mod 3

Остатков ровно три, значит, хватит трёх состояний r0, r1, r2.

Здесь блестяще видна суть конечного автомата: состояние — это класс эквивалентности всех префиксов, которые дальше ведут себя одинаково. Число может быть астрономическим, но для будущего важен только остаток. Именно так конечная память побеждает бесконечный вход.

class DFA:
    """Детерминированный конечный автомат. delta может быть частичной:
    отсутствие перехода трактуем как переход в неявную ловушку."""

    def __init__(self, states, alphabet, delta, start, accepting):
        self.states, self.alphabet = set(states), set(alphabet)
        self.delta, self.start, self.accepting = delta, start, set(accepting)

    def accepts(self, word: str) -> bool:
        q = self.start
        for ch in word:                     # ровно один проход
            if (q, ch) not in self.delta:   # попали в ловушку — дальше можно не читать
                return False
            q = self.delta[(q, ch)]
        return q in self.accepting


# Состояние = значение прочитанного префикса по модулю 3
div3 = DFA(
    states={0, 1, 2},
    alphabet={'0', '1'},
    delta={(r, b): (2 * r + int(b)) % 3 for r in (0, 1, 2) for b in ('0', '1')},
    start=0,
    accepting={0},
)

for n in (3, 6, 7, 9, 10, 12345678901234567890):
    assert div3.accepts(bin(n)[2:]) == (n % 3 == 0)
print("DFA согласуется с арифметикой на всех проверенных числах")

Сложность. Время O(n), где n = |w|; память — O(1) сверх таблицы переходов (сама таблица O(|Q| · |Σ|)). Никаких аллокаций, никакого бэктрекинга, идеальная предсказуемость. Именно поэтому DFA зашивают в сетевые железки, в лексеры и в parsers критичного пути.

Недетерминированный конечный автомат (NFA)

Определение. NFA — пятёрка (Q, Σ, δ, q0, F), где δ: Q × (Σ ∪ {ε}) -> P(Q). То есть из состояния по символу можно попасть в множество состояний (возможно, пустое), и есть ε-переходы, не потребляющие входного символа.

L(M) = { w : существует хотя бы один путь из q0, помеченный w, в состояние из F }

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

Теорема (Рабин — Скотт, 1959). Для любого NFA существует эквивалентный DFA. Классы распознаваемых языков совпадают.

Доказательство конструктивно и называется конструкцией подмножеств (subset construction / powerset construction): состояния DFA — это подмножества Q, начальное состояние — ε-замыкание {q0}, переход — δ_D(S, a) = ε-замыкание(объединение δ(s, a) по s ∈ S), принимающие — те S, что пересекаются с F.

Цена. Подмножеств 2^|Q|, и эта граница достижима. Классический пример: язык L_k = { w ∈ {a,b}* : k-й символ с конца равен 'a' }. NFA распознаёт его k+2 состояниями («угадай, что это тот самый символ, и отсчитай k-1 дальше»). А любой DFA обязан помнить последние k символов целиком — потому что до конца слова он не знает, где конец, — и требует ровно 2^k состояний.

Этот выбор — не академический. Он ровно тот, который делают промышленные движки: строить DFA целиком (быстро, но экспоненциальная память), симулировать NFA (линейная память, чуть медленнее на символ) или строить DFA лениво с ограниченным кэшем — компромисс, реализованный в RE2 и в regex для Rust.

Регулярные выражения и теорема Клини

Определение (синтаксис). Регулярные выражения над Σ определяются индуктивно:

∅            -- обозначает язык {}
ε            -- обозначает язык {ε}
a  (a ∈ Σ)   -- обозначает язык {a}
(R | S)      -- L(R) ∪ L(S)
(R S)        -- L(R) · L(S)
(R*)         -- L(R)*

И всё. Никаких обратных ссылок, никаких lookahead, никаких \b. Это математические регулярные выражения.

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

Обе стороны конструктивны:

• RE → NFA: конструкция Томпсона. Каждой операции соответствует фрагмент автомата с ровно одним входом и одним выходом, фрагменты склеиваются ε-переходами.
• NFA → RE: метод исключения состояний (алгоритм Клини / Броззовски) — по одному выкидываем состояния, помечая рёбра регулярными выражениями. Результат может быть экспоненциально длинным.

Полный конвейер: от регулярки до DFA, руками

Соберём всё в работающий код: парсер регулярок рекурсивным спуском, конструкция Томпсона, симуляция NFA и конструкция подмножеств.

from collections import deque

# ---------- 1. Разбор регулярного выражения в AST ----------
class RegexParser:
    """Грамматика (приоритеты: * сильнее конкатенации, конкатенация сильнее |):
       alt    -> concat ('|' concat)*
       concat -> repeat*
       repeat -> atom ('*' | '+' | '?')*
       atom   -> '(' alt ')' | символ
    """

    def __init__(self, src: str):
        self.s, self.i = src, 0

    def peek(self):
        return self.s[self.i] if self.i < len(self.s) else None

    def parse(self):
        node = self.alt()
        assert self.i == len(self.s), f"лишние символы с позиции {self.i}"
        return node

    def alt(self):
        node = self.concat()
        while self.peek() == '|':
            self.i += 1
            node = ('alt', node, self.concat())
        return node

    def concat(self):
        parts = []
        while self.peek() not in (None, '|', ')'):
            parts.append(self.repeat())
        if not parts:
            return ('eps',)                       # пустая альтернатива — это ε
        node = parts[0]
        for p in parts[1:]:
            node = ('cat', node, p)
        return node

    def repeat(self):
        node = self.atom()
        while self.peek() in ('*', '+', '?'):
            op = {'*': 'star', '+': 'plus', '?': 'opt'}[self.peek()]
            self.i += 1
            node = (op, node)
        return node

    def atom(self):
        if self.peek() == '(':
            self.i += 1
            node = self.alt()
            assert self.peek() == ')', "не закрыта скобка"
            self.i += 1
            return node
        self.i += 1
        return ('sym', self.s[self.i - 1])


# ---------- 2. Конструкция Томпсона: AST -> NFA ----------
class NFA:
    """Переходы: trans[(состояние, символ_или_None)] = множество состояний.
    None означает ε-переход."""

    def __init__(self):
        self.trans, self.n = {}, 0

    def new(self) -> int:
        self.n += 1
        return self.n - 1

    def add(self, a, sym, b):
        self.trans.setdefault((a, sym), set()).add(b)


def thompson(node, nfa: NFA):
    """Возвращает (вход, выход) фрагмента. Инвариант: ровно один вход, ровно один выход."""
    kind = node[0]
    if kind == 'eps':
        i, f = nfa.new(), nfa.new(); nfa.add(i, None, f); return i, f
    if kind == 'sym':
        i, f = nfa.new(), nfa.new(); nfa.add(i, node[1], f); return i, f
    if kind == 'cat':
        i1, f1 = thompson(node[1], nfa)
        i2, f2 = thompson(node[2], nfa)
        nfa.add(f1, None, i2)                     # выход первого -> вход второго
        return i1, f2
    if kind == 'alt':
        i, f = nfa.new(), nfa.new()
        i1, f1 = thompson(node[1], nfa)
        i2, f2 = thompson(node[2], nfa)
        nfa.add(i, None, i1); nfa.add(i, None, i2)
        nfa.add(f1, None, f); nfa.add(f2, None, f)
        return i, f
    if kind == 'star':
        i, f = nfa.new(), nfa.new()
        i1, f1 = thompson(node[1], nfa)
        nfa.add(i, None, i1); nfa.add(i, None, f)   # ноль повторений
        nfa.add(f1, None, i1); nfa.add(f1, None, f) # ещё раз / выход
        return i, f
    if kind == 'opt':
        i, f = nfa.new(), nfa.new()
        i1, f1 = thompson(node[1], nfa)
        nfa.add(i, None, i1); nfa.add(i, None, f); nfa.add(f1, None, f)
        return i, f
    if kind == 'plus':                             # X+ == X X*
        i1, f1 = thompson(node[1], nfa)
        i2, f2 = thompson(('star', node[1]), nfa)
        nfa.add(f1, None, i2)
        return i1, f2
    raise ValueError(kind)


# ---------- 3. ε-замыкание и симуляция NFA ----------
def eps_closure(nfa, states):
    """Все состояния, достижимые ε-переходами. Обычный обход в глубину по графу."""
    stack, seen = list(states), set(states)
    while stack:
        s = stack.pop()
        for t in nfa.trans.get((s, None), ()):
            if t not in seen:
                seen.add(t); stack.append(t)
    return frozenset(seen)


def simulate_nfa(nfa, start, accept, word) -> bool:
    """Симуляция ВСЕХ путей сразу: состояние симулятора = множество состояний NFA.
    Время O(|w| * |Q| * средняя степень), память O(|Q|). Бэктрекинга нет вообще."""
    cur = eps_closure(nfa, {start})
    for ch in word:
        move = set()
        for s in cur:
            move |= nfa.trans.get((s, ch), set())
        cur = eps_closure(nfa, move)
        if not cur:                                # все пути умерли
            return False
    return accept in cur


# ---------- 4. Конструкция подмножеств: NFA -> DFA ----------
def subset_construction(nfa, start, accept, alphabet) -> DFA:
    s0 = eps_closure(nfa, {start})
    index = {s0: 0}                                # подмножество NFA -> номер состояния DFA
    delta, accepting = {}, set()
    queue = deque([s0])
    while queue:
        S = queue.popleft()
        if accept in S:
            accepting.add(index[S])
        for a in alphabet:
            move = set()
            for s in S:
                move |= nfa.trans.get((s, a), set())
            T = eps_closure(nfa, move)
            if not T:
                continue                           # мёртвое подмножество не материализуем
            if T not in index:
                index[T] = len(index)
                queue.append(T)
            delta[(index[S], a)] = index[T]
    return DFA(range(len(index)), alphabet, delta, 0, accepting)


# ---------- Демонстрация ----------
nfa = NFA()
ast = RegexParser("(a|b)*abb").parse()
i0, f0 = thompson(ast, nfa)
dfa = subset_construction(nfa, i0, f0, {'a', 'b'})

print("состояний в NFA:", nfa.n)          # 14
print("состояний в DFA:", len(dfa.states)) # 5
for w in ["abb", "aabb", "babb", "abba", "ab", ""]:
    assert dfa.accepts(w) == simulate_nfa(nfa, i0, f0, w)
    print(f"{w!r:8} -> {dfa.accepts(w)}")

Вывод:

состояний в NFA: 14
состояний в DFA: 5
'abb'    -> True
'aabb'   -> True
'babb'   -> True
'abba'   -> False
'ab'     -> False
''       -> False

Взрыв подмножеств на практике легко воспроизвести. Возьмём L_k («k-й символ с конца — это a»), то есть регулярку (a|b)*a(a|b)^(k-1):

for k in range(1, 11):
    r = '(a|b)*a' + '(a|b)' * (k - 1)
    nf = NFA(); i, f = thompson(RegexParser(r).parse(), nf)
    d = subset_construction(nf, i, f, {'a', 'b'})
    print(f"k={k:2}  состояний NFA={nf.n:3}  состояний DFA={len(d.states):5}  2^k={2**k}")

k= 1  состояний NFA= 10  состояний DFA=    3  2^k=2
k= 5  состояний NFA= 34  состояний DFA=   33  2^k=32
k=10  состояний NFA= 64  состояний DFA= 1025  2^k=1024

NFA растёт линейно, DFA — экспоненциально. Ровно поэтому «скомпилируйте регулярку в DFA один раз, а потом всё будет быстро» — совет, который иногда убивает сервис по памяти.

Минимизация DFA и теорема Майхилла — Нероуда

Определение (правая конгруэнция Майхилла — Нероуда). Для языка L определим отношение на словах:

u ~_L v   <=>   для всех z ∈ Σ*:  (uz ∈ L)  <=>  (vz ∈ L)

Иными словами, u и v неразличимы, если ни одно продолжение не позволяет их отличить. Это отношение эквивалентности, согласованное с приписыванием справа.

Теорема (Майхилл — Нероуд). L регулярен ⟺ ~_L имеет конечное число классов эквивалентности. Более того, минимальный DFA для L единственен с точностью до переименования состояний, и его состояния — ровно эти классы.

Эта теорема мощнее леммы о накачке: она даёт критерий (в обе стороны), а не только необходимое условие. Хотите доказать нерегулярность — предъявите бесконечное семейство попарно различимых слов.

Пример. L = { a^n b^n : n >= 0 }. Возьмём слова a^0, a^1, a^2, .... Для i ≠ j слово z = b^i различает их: a^i b^i ∈ L, а a^j b^i ∉ L. Значит, классов бесконечно много, и L нерегулярен. Три строки — и готово.

Алгоритмически минимизация — это разбиение множества состояний на классы неразличимости. Начинаем с разбиения {F, Q\F} и уточняем: два состояния в одном классе остаются вместе, только если по каждому символу ведут в один и тот же класс.

def minimize(dfa: DFA):
    """Алгоритм Мура: уточнение разбиения до неподвижной точки.
    Время O(|Q|^2 * |Σ|) в этой наивной записи; алгоритм Хопкрофта даёт O(|Σ| * |Q| log |Q|).
    Требует ТОТАЛЬНОЙ функции переходов — добавляем состояние-ловушку."""
    states = sorted(dfa.states) + ['SINK']
    alphabet = sorted(dfa.alphabet)
    delta = {
        (q, a): ('SINK' if q == 'SINK' else dfa.delta.get((q, a), 'SINK'))
        for q in states for a in alphabet
    }
    part = {q: int(q in dfa.accepting) for q in states}   # старт: принимающие / остальные
    while True:
        # подпись состояния: его класс + классы всех преемников
        sig = {q: (part[q], tuple(part[delta[(q, a)]] for a in alphabet)) for q in states}
        codes, new = {}, {}
        for q in states:
            codes.setdefault(sig[q], len(codes))
            new[q] = codes[sig[q]]
        if len(set(new.values())) == len(set(part.values())):
            return part                                   # разбиение перестало дробиться
        part = new


part = minimize(dfa)
print(part)   # {0: 0, 1: 1, 2: 0, 3: 2, 4: 3, 'SINK': 4}

Результат: конструкция подмножеств дала 5 состояний, а классов оказалось 4 (плюс недостижимая ловушка) — состояния 0 и 2 слились. Канонический минимальный DFA для (a|b)*abb действительно имеет 4 состояния.

Зачем это в проде. Минимальный DFA — это каноническая форма языка. Отсюда: два DFA распознают один язык ⟺ их минимизации изоморфны. Это даёт полиномиальный алгоритм проверки эквивалентности регулярок — используется в тестировании конфигураций фаерволов, в проверке эквивалентности маршрутов, в верификации протоколов. Также минимизация — это буквально сжатие таблицы переходов: в DPI-железках и лексерах разница между 4000 и 400 состояний определяет, влезет ли таблица в кэш.

Лемма о накачке и границы регулярности

Лемма о накачке для регулярных языков. Если L регулярен, то существует p >= 1 (константа накачки) такое, что любое w ∈ L с |w| >= p разложимо в w = xyz, где:

1) |y| >= 1
2) |xy| <= p
3) для всех i >= 0:  x y^i z ∈ L

Почему это верно (интуиция за одну фразу). Пусть у минимального DFA p состояний. Читая слово длиной >= p, автомат посещает >= p+1 состояний, значит, по принципу Дирихле какое-то состояние повторится в первых p шагах. Кусок между двумя посещениями — это цикл в графе автомата; его можно пройти сколько угодно раз, и результат не изменится.

Критично. Лемма — необходимое, но не достаточное условие. Есть нерегулярные языки, удовлетворяющие лемме. Поэтому «слово накачивается» не доказывает регулярность. Для доказательства регулярности стройте автомат или используйте Майхилла — Нероуда.

Классическое применение. Докажем, что L = { a^n b^n } нерегулярен. Пусть регулярен, p — константа. Берём w = a^p b^p ∈ L. По условию |xy| <= p, значит, x и y состоят только из a, и y = a^k, k >= 1. Тогда xy^2 z = a^(p+k) b^p, где p + k ≠ p, то есть слово не в L. Противоречие.

Что из этого следует практически. Ни одно математически-регулярное выражение не умеет:

• считать вложенность (скобки, теги, JSON, if/else);
• сравнивать два фрагмента на равенство ({ ww });
• проверять «число a равно числу b».

Знаменитый ответ на Stack Overflow про парсинг HTML регуляркой — это, если убрать эмоции, ровно лемма о накачке.

Свойства замкнутости

Регулярные языки замкнуты почти относительно всего, и каждое замыкание — это конструкция, которую применяют в инструментах:

Особенно полезно произведение автоматов: состояния — пары, переход — покомпонентный. Так проверяют «удовлетворяет ли система спецификации» в model checking: строят произведение автомата системы и автомата отрицания свойства и проверяют пустоту. Именно это делает SPIN с LTL-формулами (на ω-словах, где вместо конечных автоматов — автоматы Бюхи).

Дополнение — единственная «дорогая» операция, и это фундаментально: чтобы сказать «ни один путь не принимает», надо перебрать все пути. Отсюда следует, что проверка эквивалентности NFA — PSPACE-полная задача (см. Теорию сложности), тогда как для DFA она полиномиальна.

Иерархия Хомского

Ноам Хомский в 1956 году классифицировал грамматики по форме правил. Получилась строгая цепочка вложений, где каждый уровень соответствует определённому классу памяти у распознавателя.

Определение (порождающая грамматика). Грамматика — четвёрка G = (V, Σ, P, S): V — нетерминалы, Σ — терминалы (V ∩ Σ = {}), P — правила вида α -> β, S ∈ V — стартовый символ. Язык L(G) — множество терминальных слов, выводимых из S.

Тип 3 (регулярные):            A -> aB   или  A -> a       (праволинейные)
Тип 2 (контекстно-свободные):  A -> β                        (слева ровно один нетерминал)
Тип 1 (контекстно-зависимые):  αAγ -> αβγ, |β| >= 1          (замена A зависит от контекста)
Тип 0 (без ограничений):       α -> β,  α содержит нетерминал

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

Контекстно-свободные грамматики и МП-автоматы

Определение (КС-грамматика). Все правила имеют вид A -> β, где A ∈ V, β ∈ (V ∪ Σ)*. Название «контекстно-свободная» означает: A можно заменить на β независимо от того, что стоит вокруг.

Пример — арифметические выражения с правильными приоритетами:

E -> E + T | E - T | T
T -> T * F | T / F | F
F -> ( E ) | число

Здесь структура грамматики кодирует семантику: то, что * привязан к T, а + к E, автоматически даёт * более высокий приоритет; то, что рекурсия левая (E -> E + T), даёт левую ассоциативность вычитания (10-2-3 — это (10-2)-3, а не 10-(2-3)).

Определение (МП-автомат, PDA). Семёрка (Q, Σ, Γ, δ, q0, Z0, F), где Γ — стековый алфавит, а δ: Q × (Σ ∪ {ε}) × Γ -> P(Q × Γ*). То есть переход смотрит на состояние, входной символ и вершину стека, и может заменить вершину на строку символов.

Теорема. Класс языков, порождаемых КС-грамматиками, совпадает с классом языков, распознаваемых недетерминированными МП-автоматами.

Важнейшая асимметрия по сравнению с конечными автоматами: детерминированные МП-автоматы СЛАБЕЕ недетерминированных. DPDA ⊊ PDA. Например, язык палиндромов { w w^R } контекстно-свободен, но не распознаётся детерминированным МП-автоматом — надо «угадать» середину. Это принципиально отличается от ситуации с DFA/NFA и объясняет, почему в парсинге приходится выбирать между «быстро и детерминированно, но не всякую грамматику» (LL, LR) и «любую грамматику, но дороже» (Earley, GLR).

Деревья разбора и неоднозначность

Определение. Грамматика неоднозначна, если существует слово с двумя разными деревьями разбора.

Каноничный пример — dangling else:

S -> if E then S | if E then S else S | other

Строка if a then if b then x else y разбирается двумя способами: else может относиться к внешнему или к внутреннему if. Реальные языки решают это внеграмматически (правило «else цепляется к ближайшему if»), в yacc/bison — через объявления приоритетов, которые фактически подавляют конфликт.

Теорема. Проблема «является ли данная КС-грамматика неоднозначной» неразрешима (сводится к проблеме соответствий Поста). Более того, существуют существенно неоднозначные языки, для которых любая грамматика неоднозначна, например { a^i b^j c^k : i = j или j = k }.

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

CYK: разбор любой КС-грамматики за куб

Алгоритм Кока — Янгера — Касами — это динамическое программирование по подстрокам. Требует грамматику в нормальной форме Хомского (правила A -> BC и A -> a), к которой приводится любая КС-грамматика.

# Язык Дика (непустые правильные скобочные последовательности) в НФХ.
# S -> LR | LT | SS ,  T -> SR ,  L -> '(' ,  R -> ')'
GRAMMAR   = {'S': [('L', 'R'), ('L', 'T'), ('S', 'S')], 'T': [('S', 'R')]}
TERMINALS = {'L': '(', 'R': ')'}


def cyk(word, grammar=GRAMMAR, terminals=TERMINALS, start='S') -> bool:
    """table[i][j] = множество нетерминалов, выводящих подстроку word[i:j].
    Время O(n^3 * |G|), память O(n^2 * |V|)."""
    n = len(word)
    if n == 0:
        return False
    table = [[set() for _ in range(n + 1)] for _ in range(n + 1)]

    for i, ch in enumerate(word):                 # база: подстроки длины 1
        for A, t in terminals.items():
            if t == ch:
                table[i][i + 1].add(A)

    for length in range(2, n + 1):                # по возрастанию длины подстроки
        for i in range(0, n - length + 1):
            j = i + length
            for k in range(i + 1, j):             # точка разреза
                for A, rules in grammar.items():
                    for B, C in rules:
                        if B in table[i][k] and C in table[k][j]:
                            table[i][j].add(A)
    return start in table[0][n]


for w in ["()", "(())", "()()", "(()())", "((()))", "(()", ")("]:
    print(f"{w:8} {cyk(w)}")

()       True
(())     True
()()     True
(()())   True
((()))   True
(()      False
)(       False

Обратите внимание: этот язык невозможен для регулярки (глубина вложенности неограниченна), но легко даётся стеку. И заметьте цену: O(n^3) против O(n) у DFA. Это и есть плата за подъём на один уровень иерархии.

Лемма о накачке для КС-языков

Формулировка сложнее: для КС-языка существует p такое, что любое w ∈ L, |w| >= p, разложимо как w = uvxyz, где |vy| >= 1, |vxy| <= p, и u v^i x y^i z ∈ L для всех i >= 0. Накачиваются два куска синхронно — потому что в достаточно глубоком дереве разбора какой-то нетерминал повторяется на пути от корня к листу, и поддерево между двумя вхождениями можно вставлять сколько угодно раз.

Применение. { a^n b^n c^n } не контекстно-свободен: v и y не могут одновременно покрыть все три буквы (|vxy| <= p), значит, при накачке баланс сломается. Это тот самый язык, из-за которого «переменная должна быть объявлена до использования» не выражается КС-грамматикой — и почему компиляторы делают семантический анализ отдельным проходом после парсинга.

Не замкнуты. КС-языки не замкнуты относительно пересечения и дополнения. Контрпример: {a^n b^n c^m} и {a^m b^n c^n} контекстно-свободны, а их пересечение — {a^n b^n c^n} — нет.

Технологии разбора: как выбирать

LL(k) — рекурсивный спуск. Разбор сверху вниз: по k следующим токенам решаем, какое правило применить. Требует, чтобы грамматика была без левой рекурсии и с непересекающимися множествами FIRST. Плюсы: пишется руками, читается как грамматика, даёт превосходные сообщения об ошибках, легко встроить восстановление. Минусы: класс грамматик узкий; левую рекурсию надо устранять вручную, что портит естественную запись левоассоциативных операторов.

# LL(1)-парсер арифметики + вычисление на лету.
# E  -> T E'      E' -> ('+'|'-') T E' | ε
# T  -> F T'      T' -> ('*'|'/') F T' | ε
# F  -> '(' E ')' | число
# Циклы while ниже — ровно развёртка хвостовой рекурсии E' и T'.
import re

TOKEN_RE = re.compile(r"\s*(?:(\d+)|(.))")


def tokenize(src):
    out, pos = [], 0
    while pos < len(src):
        m = TOKEN_RE.match(src, pos)
        if not m:
            break
        pos = m.end()
        if m.group(1):
            out.append(('num', int(m.group(1))))
        elif m.group(2).strip():
            out.append((m.group(2), m.group(2)))
    out.append(('$', None))
    return out


class LL1:
    def __init__(self, tokens):
        self.t, self.i = tokens, 0

    def look(self):
        return self.t[self.i][0]

    def take(self, kind):
        assert self.look() == kind, f"ожидалось {kind}, встречено {self.look()}"
        self.i += 1
        return self.t[self.i - 1][1]

    def expr(self):                      # левоассоциативность через цикл, не через рекурсию
        v = self.term()
        while self.look() in ('+', '-'):
            op = self.take(self.look())
            r = self.term()
            v = v + r if op == '+' else v - r
        return v

    def term(self):
        v = self.factor()
        while self.look() in ('*', '/'):
            op = self.take(self.look())
            r = self.factor()
            v = v * r if op == '*' else v // r
        return v

    def factor(self):
        if self.look() == '(':
            self.take('('); v = self.expr(); self.take(')'); return v
        return self.take('num')


for src in ["2+3*4", "(2+3)*4", "10-2-3", "2*(3+4)*5"]:
    print(f"{src:12} = {LL1(tokenize(src)).expr()}")

2+3*4        = 14
(2+3)*4      = 20
10-2-3       = 5
2*(3+4)*5    = 70

LR(k) / LALR — восходящий разбор. Строим автомат над «пунктированными правилами» (items), в стеке держим уже свёрнутые фрагменты. Класс LR(1) строго шире LL(k) и покрывает почти все реальные языки, разбор за O(n). Минусы: таблица генерируется инструментом, конфликты (shift/reduce, reduce/reduce) диагностируются в терминах внутренностей автомата, а не грамматики; сообщения об ошибках пользователю по умолчанию бедные. LALR — сжатие таблицы LR(1) слиянием состояний с одинаковым ядром: меньше памяти, но появляются новые reduce/reduce-конфликты. Это yacc, bison, goyacc.

PEG / packrat. Синтаксис похож на КС-грамматику, но оператор выбора упорядоченный: A / B пробует A, и если получилось — B не рассматривается никогда. Это устраняет неоднозначность по построению, но меняет семантику: PEG-грамматика может молча не распознавать то, что вы имели в виду. Packrat-мемоизация даёт O(n) время ценой O(n) памяти. PEG-языки и КС-языки — несравнимые классы: PEG умеет {a^n b^n c^n}, но неизвестно, всякий ли КС-язык выражается PEG. См. оригинальную работу Форда.

Earley и GLR. Разбирают любую КС-грамматику, включая неоднозначные, выдавая лес разбора. Earley — O(n^3) в худшем случае, O(n^2) для однозначных, O(n) для LR-подобных. GLR — то же самое, но как LR-автомат с расщеплением стека; на этом построен tree-sitter, который парсит инкрементально и терпимо к ошибкам — поэтому и живёт в редакторах.

Лексер и парсер: почему их разделяют

Разделение — не традиция, а инженерная оптимизация, обоснованная теорией: регулярный уровень на порядок дешевле контекстно-свободного. Числа, идентификаторы, строковые литералы и комментарии — регулярны, значит их можно съесть DFA за один проход с O(1) памяти. Отдав это парсеру, вы заставили бы дорогой стековый механизм работать на каждый символ. Плюс лексер выкидывает пробелы и комментарии, сокращая вход парсера в разы.

Правило максимального совпадения (maximal munch): лексер берёт самый длинный подходящий токен. Отсюда классические казусы: x---y разбирается как x-- - y, а в старом C++ vector<vector<int>> ломался из-за >>.

Регулярки в реальном мире: чем PCRE отличается от математики

Самая дорогая ошибка на этой территории: путать «регулярное выражение» из теории и «regex» из библиотеки.

Современные regex-движки (PCRE, java.util.regex, re в Python, .NET, JS) поддерживают конструкции, выводящие их за пределы регулярных языков:

• Обратные ссылки: (a*)b\1 распознаёт { a^n b a^n } — нерегулярный язык. С обратными ссылками задача поиска совпадения становится NP-полной.
• Lookahead / lookbehind: пересечение и дополнение «в синтаксисе». Само по себе не выводит за регулярные языки (эти операции замкнуты), но ломает наивную компиляцию в NFA.
• Рекурсивные шаблоны ((?R) в PCRE): это уже фактически КС-грамматика в маске регулярки.

Ценой этого стала реализация через бэктрекинг, а бэктрекинг имеет экспоненциальный худший случай. Это ReDoS — regular expression denial of service.

import re, time

pat = re.compile(r"^(a+)+b$")     # катастрофический бэктрекинг: (a+)+ неоднозначно разбивает вход
for n in (18, 20, 22, 24, 26):
    t = time.perf_counter()
    pat.match("a" * n)            # совпадения нет — движок обязан перебрать все разбиения
    print(f"n={n}  {time.perf_counter() - t:.4f} c")

n=18  0.0077 c
n=20  0.0349 c
n=22  0.1283 c
n=24  0.5163 c
n=26  2.0294 c

Время удваивается на каждый добавленный символ. 40 символов — часы. Это 2^n, и именно так уронили Cloudflare 2 июля 2019 — одна регулярка в WAF съела CPU на всём глобальном фронте.

Почему это вообще возможно? Потому что теорема Клини гарантирует линейную симуляцию, а бэктрекинг ею не пользуется. Симуляция NFA множеством состояний (как в нашем simulate_nfa выше) на том же входе отработала бы за O(n·m) — она просто не рассматривает разбиения по отдельности. Ключевая статья на эту тему — Russ Cox, «Regular Expression Matching Can Be Simple And Fast», обязательная к прочтению.

Что делать инженеру.

1. Если регулярка применяется к недоверенному вводу — используйте движок с гарантией линейного времени: RE2 (C++), regexp в стандартной библиотеке Go, крейт regex в Rust, re2 в Python через биндинги. Они сознательно не поддерживают обратные ссылки — потому что с ними линейность недостижима.
2. Если движок с бэктрекингом неизбежен — ставьте таймаут (Regex в .NET принимает matchTimeout, в Java его нет — оборачивайте сами), избегайте вложенных кванторов (x+)+, (x*)*, (x|y)* с пересекающимися альтернативами.
3. Прогоняйте свои паттерны через детекторы: safe-regex, recheck, встроенные линтеры Semgrep/CodeQL.
4. Не проверяйте регуляркой то, что нерегулярно. Валидация JSON, HTML, вложенных структур — только парсером.

Где эта теория работает в проде

Лексический анализ. flex, re2c, ANTLR-лексеры — всё это генераторы DFA из набора регулярок. Правило «первое совпавшее правило + максимальная длина» реализуется как один общий DFA с пометками принимающих состояний.

Сетевая безопасность и DPI. Snort/Suricata компилируют тысячи сигнатур в общие автоматы (Aho — Corasick для строк, гибридные DFA/NFA для регулярок). Здесь минимизация — вопрос жизни и смерти: таблица должна поместиться в кэш или TCAM.

Валидация протоколов и state machines. Жизненный цикл заказа, TCP-конечный автомат, стейт-машина UI (XState), Saga в распределённых системах — это буквально DFA. Формализация даёт бесплатно: проверку достижимости состояний, обнаружение мёртвых состояний, генерацию тестов покрытием переходов.

Верификация и model checking. LTL-формула компилируется в автомат Бюхи над бесконечными словами; система тоже автомат; проверяется пустота пересечения системы с отрицанием свойства. Это SPIN, TLA+ (через TLC), инструменты верификации железа. Красивый теоретический факт: star-free языки = апериодические синтаксические моноиды = LTL = логика первого порядка с порядком (теоремы Шютценберже и Кампа) — тот случай, когда алгебра, логика и автоматы оказываются одним и тем же объектом.

Обработка естественного языка и морфология. Конечные преобразователи (FST) — автоматы, выдающие выход, а не только «да/нет». На них построены морфологические анализаторы, транслитерация, нормализация текста; библиотека OpenFst — индустриальный стандарт. Токенизаторы вроде BPE в LLM формально ближе к жадному максимальному совпадению по словарю, чем к DFA, но идея «один проход слева направо с конечной памятью» та же.

Базы данных и потоки. LIKE-шаблоны компилируются в автоматы; MATCH_RECOGNIZE в SQL:2016 (и в Flink) — это буквально «регулярное выражение над строками таблицы», распознавание паттернов в потоке событий конечным автоматом.

Компиляторы и инструменты разработчика. Всё дерево от лексера до AST — это иерархия Хомского в действии. И граница между уровнями объясняет структуру компилятора: лексер (регулярный) → парсер (КС) → семантический анализ (то, что за пределами КС: типы, области видимости, объявления). Именно поэтому «переменная не объявлена» — не синтаксическая ошибка.

Типичные заблуждения

«Регулярки в PCRE — это регулярные языки». Нет. Обратные ссылки делают их существенно мощнее и алгоритмически хуже. Из «мой паттерн — регулярка» не следует «он выполнится быстро».

«Регуляркой можно распарсить X, если постараться». Если X содержит неограниченную вложенность — доказуемо нельзя. Не «сложно», а нельзя, по лемме о накачке.

«DFA всегда быстрее NFA, надо детерминизировать». Быстрее на символ — да. Но построение может съесть 2^n памяти, а на коротких входах время построения перевесит выигрыш. Промышленные движки строят DFA лениво и с вытеснением кэша.

«Если лемма о накачке выполняется, язык регулярен». Лемма — только необходимое условие. Критерий — Майхилл — Нероуд.

«Если генератор парсеров не выдал конфликтов, грамматика однозначна». Обратное неверно: отсутствие конфликтов LALR означает лишь, что эта таблица детерминирована. Проверка однозначности вообще неразрешима.

«Недетерминизм — это про параллелизм или про случайность». Это про квантор существования по путям. При симуляции никакой параллельности нет: одно множество состояний, один проход.

«NFA и DFA различаются по мощности». Не различаются (Рабин — Скотт), различаются только по размеру. А вот для МП-автоматов различаются по-настоящему: DPDA ⊊ PDA.

«ε — это то же самое, что пустое множество». {} и {ε} — разные языки, и путаница между ними порождает бесконечные циклы в while match: ....

Мини-итог

• Язык — это множество слов; языков несчётно много, описуемых — счётно. Всё интересное происходит на этом островке.
• Регулярные языки = DFA = NFA = регулярные выражения (Клини). Память O(1), время O(n), замкнутость почти на всём, каноническая минимальная форма, разрешимая эквивалентность.
• Границу регулярности проверяют леммой о накачке (необходимое условие) или Майхиллом — Нероудом (критерий). Считать вложенность и сравнивать половины слова конечная память не умеет.
• NFA → DFA возможно всегда, но стоит до 2^n. Практика — ленивая детерминизация с кэшем.
• Контекстно-свободные языки = недетерминированные МП-автоматы: стек даёт вложенность ценой O(n^3) в общем случае. Детерминированные МП-автоматы строго слабее — отсюда зоопарк LL/LR/PEG/Earley/GLR.
• Неоднозначность и эквивалентность КС-грамматик неразрешимы — инструменты дают только частичные ответы.
• Иерархия Хомского — это иерархия по памяти распознавателя. Выбирая формализм, вы выбираете, сколько памяти и времени готовы платить за выразительность.
• В инженерной жизни это выглядит как: лексер — DFA, парсер — PDA, семантика — за пределами КС, а регулярка на недоверенном вводе — только с линейной гарантией.

Источники

• John Hopcroft, Rajeev Motwani, Jeffrey Ullman. Introduction to Automata Theory, Languages, and Computation, 3rd ed., Pearson, 2006 — канонический учебник, «книга Хопкрофта».
• Michael Sipser. Introduction to the Theory of Computation, 3rd ed., Cengage, 2012 — лучшие доказательства лемм о накачке, очень читаемо.
• Alfred Aho, Monica Lam, Ravi Sethi, Jeffrey Ullman. Compilers: Principles, Techniques, and Tools, 2nd ed. («книга дракона») — главы 3 и 4: лексический анализ, LL и LR во всех деталях.
• Noam Chomsky. Three models for the description of language, IRE Transactions on Information Theory, 1956 — статья, с которой началась иерархия.
• Michael Rabin, Dana Scott. Finite Automata and Their Decision Problems, IBM Journal, 1959 — конструкция подмножеств, Тьюринговская премия.
• Ken Thompson. Regular Expression Search Algorithm, CACM 1968 — та самая конструкция.
• Russ Cox. Regular Expression Matching Can Be Simple And Fast и продолжения — почему бэктрекинг был ошибкой индустрии.
• Bryan Ford. Parsing Expression Grammars: A Recognition-Based Syntactic Foundation, POPL 2004.
• Terence Parr et al. Adaptive LL(*) Parsing: The Power of Dynamic Analysis, OOPSLA 2014 — алгоритм внутри ANTLR 4.
• Документация RE2, regexp в Go, re в Python, tree-sitter, OpenFst.
• Cloudflare. Details of the Cloudflare outage on July 2, 2019 — ReDoS в проде, разбор по шагам.
• OWASP. Regular expression Denial of Service — ReDoS.

Что дальше

Автоматы — это мир жёстких «да/нет»: слово либо в языке, либо нет. Но огромная часть инженерных решений принимается там, где определённости не бывает вовсе: сколько запросов придёт в пике, какова вероятность коллизии хешей, значимо ли отличие в A/B-тесте, насколько можно верить метрике на 200 наблюдениях. Следующая статья даёт аппарат для рассуждений в условиях неопределённости — и он ровно так же строг, как всё, что мы делали выше.

Теория вероятностей и статистика для инженера