Минимизация ДКА: какие состояния действительно различаются

Если умеешь предъявить различающее продолжение и построить фактор-автомат, листай до «Теперь сам».

Как думаешь, достаточно ли одинаковых ближайших переходов

Два состояния сейчас не принимающие. На следующем символе оба тоже попадают в не принимающие. Можно ли их слить? Продолжение из двух или ста символов ещё может привести одно к принятию, другое к отказу. Совпадения поведения на ограниченном числе шагов недостаточно, пока не доказана устойчивость разбиения для всех будущих продолжений.

На что это похоже

Представь два состояния меню банкомата. Они могут выглядеть одинаково, но после одной и той же последовательности нажатий первое выдаёт чек, а второе возвращается к вводу суммы. Значит они различны для пользователя. Если никакая будущая последовательность нажатий не различает их результат, две внутренние метки описывают одну и ту же наблюдаемую ситуацию.

Механизм: от пустого продолжения ко всем продолжениям

Пустая строка уже различает принимающее и непринимающее состояние. Это начальное разбиение. Для каждого состояния составим подпись: прежний класс и классы целей переходов по всем символам алфавита. Разные подписи означают новое разделение. Состояния из разных прежних классов не соединяются обратно.

После первого уточнения учитываются продолжения длины один, после следующего - длины два. Если разбиение больше не меняется, переходы из любого его класса по одному символу ведут в один определённый класс. По индукции одинаково обрабатывается любая длина продолжения. Устойчивые классы действительно эквивалентны, а не просто выглядят похожими в таблице.

Каждое строгое уточнение увеличивает число классов; их не больше числа состояний n. Прямой вариант Мура выполняет не больше n-1 строгих уточнений, обрабатывая переходы каждой итерации. Для большого автомата алгоритм Хопкрофта уточняет по меньшим разделяющим частям и достигает O(|Σ|n log n), где Σ - алфавит. Минимизация не заменяет детерминизацию: к НКА эти подписи напрямую неприменимы.

Правило

Сливай состояния по одинаковому языку будущих продолжений, а не по имени, текущему признаку или одному переходу. До минимизации удали недостижимые состояния и сделай автомат полным. Пустой переход в таблице требует явного состояния-ловушки, иначе сравниваются разные модели.

Разбор: пять состояний превращаются в два

from itertools import product

transitions = [[2, 1], [2, 3], [2, 3], [0, 1], [4, 4]]
accepting = {1, 3, 4}
start = 0
reachable = {start}
frontier = [start]
while frontier:
    q = frontier.pop()
    for target in transitions[q]:
        if target not in reachable:
            reachable.add(target)
            frontier.append(target)
blocks = [reachable & accepting, reachable - accepting]
blocks = [b for b in blocks if b]
while True:
    owner = {q: i for i, block in enumerate(blocks) for q in block}
    groups = {}
    for q in sorted(reachable):
        signature = (owner[q], *(owner[t] for t in transitions[q]))
        groups.setdefault(signature, set()).add(q)
    refined = list(groups.values())
    if {frozenset(b) for b in refined} == {frozenset(b) for b in blocks}:
        break
    blocks = refined
owner = {q: i for i, block in enumerate(blocks) for q in block}
small = [[owner[t] for t in transitions[min(block)]] for block in blocks]
small_accepting = {owner[q] for q in reachable & accepting}


def accepts(table, finals, initial, word):
    q = initial
    for letter in word:
        q = table[q][letter]
    return q in finals


checked = 0
for length in range(8):
    for word in product((0, 1), repeat=length):
        one = accepts(transitions, accepting, start, word)
        two = accepts(small, small_accepting, owner[start], word)
        assert one == two
        checked += 1
print("Достижимые:", sorted(reachable))
print("Классы:", sorted(sorted(b) for b in blocks))
print("Состояний после сжатия:", len(blocks))
print("Проверено строк:", checked)

Достижимые: [0, 1, 2, 3]
Классы: [[0, 2], [1, 3]]
Состояний после сжатия: 2
Проверено строк: 255

Недостижимое состояние четыре удаляется, даже если оно принимающее. Оставшиеся состояния делятся на два класса: принятие зависит только от последнего символа. Программа проверяет исходный и сжатый автомат на всех строках длины до семи. Эта конечная проверка полезна для реализации; доказательство для всех длин обеспечивается устойчивостью разбиения.

Разбор: различимость объясняет минимальность

Для языка двоичных строк, оканчивающихся единицей, состояния «последняя единица» и «остальное» различимы пустым продолжением: первое принимает, второе нет. Значит автомат не может иметь одно состояние. Два состояния достаточны по построению, поэтому найден минимум.

В общем случае теорема Майхилла-Нероуда рассматривает эквивалентность уже прочитанных префиксов: u и v эквивалентны, если для любой строки z принадлежность uz языку совпадает с принадлежностью vz. Каждому классу нужен отдельный различимый контекст. Конечное число классов даёт ДКА, а бесконечное означает нерегулярность. Здесь это продолжает знакомое доказательство через неограниченное число различимых начал.

Единственность минимального автомата относится к структуре переходов, а не к выбранным именам или порядку строк таблицы. Две программы минимизации могут выдать разные номера состояний и всё же построить один автомат с точностью до изоморфизма.

Что ломается без этого

Если не удалить недостижимые состояния, останутся классы, не влияющие на язык из начального состояния. Если проверять лишь одну букву, можно пропустить различающее продолжение большей длины. И нельзя после слияния выбрать переход из случайного представителя без проверки устойчивости: именно она гарантирует одинаковый класс цели для всех представителей.

Зачем это в работе

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

Теперь сам

Два состояния не принимающие. По символу a первое ведёт в принимающее, второе в непринимающее. Можно ли их слить? А если различается лишь переход через ещё одну промежуточную пару состояний?