Недетерминированный автомат (НКА)

Недетерминированный автомат может «расщепляться» на несколько вариантов одновременно — это делает его удобнее для проектирования, не добавляя мощности.

НКА — недетерминированный конечный автомат: из состояния по символу может вести несколько переходов (или ни одного); строка принята, если существует хотя бы один путь в принимающее состояние.

Чем НКА отличается от ДКА

В ДКА δ(q, a) даёт ровно одно состояние. В НКА δ(q, a) даёт множество состояний — может быть пустым, одним или несколькими. Формально δ: Q × Σ → 2^Q (в степень множества состояний). Автомат как бы пробует все варианты параллельно. Критерий принятия меняется радикально: строка принимается, если хотя бы один из возможных путей заканчивается в принимающем состоянии. Если все пути ведут в тупик или в непринимающие состояния — отвергается.

Эта «магия выбора» не даёт НКА распознавать больше языков, чем ДКА (мы докажем это в следующем разделе), но даёт огромное удобство построения: автоматы получаются меньше и нагляднее.

Пример: «оканчивается на 01»

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

      0,1
     ┌──┐
     │  v
  ──>(q0) --0--> (q1) --1--> ((q2))

((q2)) — принимающее. Петля 0,1 на q0 = «читаем что угодно,
пока не решим: вот сейчас начнётся хвост 01».

Заметьте: из q₀ по символу 0 есть два перехода — остаться в q₀ (петля) и уйти в q₁. Это и есть недетерминизм. В ДКА так нельзя. Таблица переходов НКА (в клетках — множества):

состояние	0	1
→ q0	{q0, q1}	{q0}
q1	∅	{q2}
q2	∅	∅

Симуляция НКА: множество текущих состояний

Как симулировать «параллельные пути» на обычном детерминированном компьютере? Держим множество состояний, в которых автомат может находиться сейчас. На каждом символе заменяем его объединением всех достижимых состояний. В конце проверяем, пересекается ли множество с принимающими.

def run_nfa(delta, start, accept, word):
    current = {start}
    for ch in word:
        nxt = set()
        for st in current:
            nxt |= delta.get((st, ch), set())  # объединяем все пути
        current = nxt
    return bool(current & accept)

# НКА: оканчивается на 01
delta = {
    ("q0", "0"): {"q0", "q1"}, ("q0", "1"): {"q0"},
    ("q1", "1"): {"q2"},
}
for w in ["01", "1101", "010", "0", "00101"]:
    ok = run_nfa(delta, "q0", {"q2"}, w)
    print(f"{w:>6} -> {'принята' if ok else 'отвергнута'}")

Вывод:

    01 -> принята
  1101 -> принята
   010 -> отвергнута
     0 -> отвергнута
 00101 -> принята

Строка «010» отвергнута (оканчивается на 0), «00101» принята (хвост 01). Множество состояний — это как раз все одновременно живущие «копии» автомата.

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

Недетерминизм — приём мышления, а не реального железа. Настоящий процессор детерминирован, поэтому симуляция держит множество состояний размером до |Q|. Можно представить, что в принимающем состоянии сидит «оракул», который заранее знает правильные ходы; или что автомат на каждом ветвлении клонируется и все клоны бегут параллельно. Оба образа эквивалентны критерию «существует принимающий путь». Именно поэтому НКА удобен: проектируя его, вы откладываете выбор «на потом», а не просчитываете все случаи как в ДКА.

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

Считать, что НКА мощнее ДКА. Нет: они распознают ровно один класс языков — регулярные. Удобство построения — да, новая мощность — нет.

Требовать, чтобы все пути приняли. Достаточно одного принимающего пути. «Все пути отвергают» нужно лишь для того, чтобы строка была отвергнута.

Забывать про тупики. Если δ(q, a) = ∅, эта ветвь «умирает» — она просто исчезает из множества, а не отвергает всю строку.

Итог

В НКА из состояния по символу может вести несколько переходов или ни одного: δ: Q × Σ → 2^Q.
Строка принята, если существует хотя бы один путь в принимающее состояние.
Симуляция — множество текущих состояний, обновляемое объединением на каждом символе.
НКА не мощнее ДКА, но часто компактнее и нагляднее при построении.