Минимизация ДКА

У каждого регулярного языка есть единственный самый маленький ДКА. Минимизация находит его, слив неразличимые состояния.

Минимизация ДКА — построение эквивалентного автомата с наименьшим числом состояний путём слияния состояний, неразличимых по поведению.

Когда два состояния «одинаковы»

Два состояния p и q называются эквивалентными, если для любой строки w автомат, стартовав из p или из q, одинаково решает — принять или отвергнуть. Проще: из p и q нельзя «различить» язык. Такие состояния — дубликаты, их можно слить в одно без изменения языка. Минимальный ДКА получается, когда все дубликаты слиты. Замечательный факт: для каждого регулярного языка минимальный ДКА единственен с точностью до переименования состояний (теорема Майхилла-Нероуда). Это делает минимальный ДКА канонической формой языка — по нему можно проверять эквивалентность двух автоматов.

Алгоритм разбиения

Классический алгоритм Хопкрофта работает «сверху вниз», уточняя разбиение состояний на классы:

Начальное разбиение — два класса: принимающие F и непринимающие Q\F (их точно нельзя слить — ε их различает).
Берём класс и символ a. Если внутри класса разные состояния по a уходят в разные классы — этот класс надо расщепить.
Повторяем, пока разбиение не перестанет меняться.
Каждый финальный класс — одно состояние минимального ДКА.

Σ={a,b}. Состояния: q0,q1,q2,q3. Принимающее: q3.
Начало: {q0,q1,q2} | {q3}
Проверяем по символам, какие уходят в класс {q3} → расщепляем,
пока классы стабильны. Эквивалентные состояния схлопываются.

Минимизация на Python

Реализуем разбиение состояний. Возьмём ДКА с заведомым дубликатом и убедимся, что он схлопнется.

def minimize(states, alphabet, delta, accept):
    # начальное разбиение: принимающие и остальные
    P = [set(accept), set(states) - set(accept)]
    P = [b for b in P if b]
    def class_of(s, part):
        for i, b in enumerate(part):
            if s in b:
                return i
    changed = True
    while changed:
        changed = False
        newP = []
        for block in P:
            groups = {}
            for s in block:
                sig = tuple(class_of(delta[(s, c)], P) for c in alphabet)
                groups.setdefault(sig, set()).add(s)
            if len(groups) > 1:
                changed = True
            newP.extend(groups.values())
        P = newP
    return P

states = ["A", "B", "C", "D"]
# B и C ведут себя одинаково (дубликаты)
delta = {
    ("A","0"):"B", ("A","1"):"C",
    ("B","0"):"D", ("B","1"):"D",
    ("C","0"):"D", ("C","1"):"D",
    ("D","0"):"D", ("D","1"):"D",
}
classes = minimize(states, "01", delta, {"D"})
print("классов (состояний минимального ДКА):", len(classes))
for c in sorted(map(sorted, classes)):
    print(c)

Вывод:

классов (состояний минимального ДКА): 3
['A']
['B', 'C']
['D']

Состояния B и C слились в один класс — они вели себя идентично. Из 4 состояний осталось 3: это и есть минимальный ДКА.

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

Почему минимум единственен? Теорема Майхилла-Нероуда связывает состояния минимального ДКА с классами эквивалентности строк: две строки эквивалентны, если их любым одинаковым продолжением нельзя различить (обе ведут в L или обе нет). Число таких классов — индекс языка. Если он конечен — язык регулярен, и минимальный ДКА имеет ровно столько состояний, сколько классов. Это даёт ещё один критерий не-регулярности: если классов бесконечно много (как у aⁿbⁿ, где каждое aⁿ — свой класс), язык не регулярен.

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

Минимизировать НКА. Алгоритм работает на ДКА. Минимальный НКА — вообще трудная (PSPACE) задача и не единственен. Сначала детерминизируйте.

Забыть про недостижимые состояния. Перед минимизацией удалите состояния, недостижимые из старта — иначе они засорят результат.

Слить принимающее с непринимающим. Они различимы пустой строкой, поэтому стартовое разбиение всегда отделяет F от остальных.

Итог

Эквивалентные состояния неразличимы никакой строкой — их можно слить без изменения языка.
Алгоритм минимизации уточняет разбиение состояний, начиная с {принимающие} | {остальные}.
Минимальный ДКА единственен (Майхилл-Нероуд) — это каноническая форма регулярного языка.
Число классов эквивалентности конечно ⇔ язык регулярен; бесконечно ⇒ не регулярен.