Детерминизация: построение подмножеств

Любой НКА можно превратить в эквивалентный ДКА — состояния нового автомата будут множествами состояний старого.

Построение подмножеств (subset construction) — алгоритм детерминизации: состояния ДКА — это подмножества состояний исходного НКА.

Идея: множество как состояние

В прошлом разделе мы симулировали НКА, держа множество текущих состояний. Гениальная мысль: а давайте объявим каждое такое множество отдельным состоянием нового, детерминированного автомата. Тогда у НКА с n состояниями получится ДКА, у которого до 2ⁿ состояний (все подмножества). Этот ДКА распознаёт ровно тот же язык — значит, ДКА и НКА эквивалентны по мощности. Недетерминизм — лишь удобство записи, а не новая вычислительная сила.

Алгоритм: стартовое состояние ДКА — ε-замыкание {q₀}. Для состояния-множества S и символа a новое состояние — это объединение δ(s, a) по всем s ∈ S (плюс ε-замыкание, если есть ε-переходы). Принимающее состояние ДКА — любое множество, содержащее хотя бы одно принимающее состояние НКА.

Пример детерминизации

Возьмём НКА «оканчивается на 01» из прошлого раздела: переходы q0--0-->{q0,q1}, q0--1-->{q0}, q1--1-->{q2}, принимающее q2. Прогоним построение подмножеств:

старт: A = {q0}
A={q0}      --0--> {q0,q1} = B     --1--> {q0} = A
B={q0,q1}   --0--> {q0,q1} = B     --1--> {q0,q2} = C
C={q0,q2}   --0--> {q0,q1} = B     --1--> {q0} = A
принимающие ДКА: те, что содержат q2  →  только C

получили ДКА из 3 состояний {A, B, C}

Алгоритм на Python

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

def subset_construction(delta, start, accept, alphabet):
    def move(states, ch):
        out = set()
        for s in states:
            out |= delta.get((s, ch), set())
        return frozenset(out)

    start_set = frozenset({start})
    dfa, queue, seen = {}, [start_set], {start_set}
    while queue:
        S = queue.pop()
        for ch in alphabet:
            T = move(S, ch)
            dfa[(S, ch)] = T
            if T not in seen:
                seen.add(T); queue.append(T)
    dfa_accept = {S for S in seen if S & accept}
    return dfa, dfa_accept

nfa = {("q0","0"):{"q0","q1"}, ("q0","1"):{"q0"}, ("q1","1"):{"q2"}}
dfa, acc = subset_construction(nfa, "q0", {"q2"}, "01")
print("состояний в ДКА:", len({s for (s, _) in dfa} | {t for t in dfa.values()}))
print("принимающих:", len(acc))
# проверим строку 1101 шаг за шагом
S = frozenset({"q0"})
for ch in "1101":
    S = dfa[(S, ch)]
print("1101 принята:", bool(S & {"q2"}))

Вывод:

состояний в ДКА: 3
принимающих: 1
1101 принята: True

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

Экспоненциальный рост 2ⁿ — это верхняя оценка, в худшем случае. Часто достижимых множеств гораздо меньше (в нашем примере из потенциальных 8 подмножеств реально появились лишь 3). Но взрыв бывает реальным: классический язык «n-й символ с конца равен 1» требует НКА из n+1 состояния, а его минимальный ДКА — 2ⁿ состояний. Это фундаментальная цена детерминизма: чтобы избавиться от «угадывания», ДКА вынужден помнить все возможные комбинации, что и кодируется множествами.

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

Забыть ε-замыкание. Если в НКА есть ε-переходы, и стартовое множество, и каждый результат move нужно ε-замыкать.

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

Строить все 2ⁿ состояний наперёд. Стройте только достижимые множества (как в коде — через очередь), иначе раздуете автомат бесполезными состояниями.

Итог

Построение подмножеств превращает НКА в эквивалентный ДКА; состояния ДКА — множества состояний НКА.
Старт — ε-замыкание {q₀}; принимающие — множества, содержащие принимающее состояние НКА.
В худшем случае ДКА имеет до 2ⁿ состояний, но строить надо только достижимые.
Следствие: ДКА и НКА эквивалентны — оба распознают регулярные языки.