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

Вы написали регулярное выражение для валидации email и конвертировали его в DFA. Получилось 47 состояний. Но оказывается, достаточно 12. Остальные 35 - «клоны», выполняющие одну и ту же работу. Минимизация DFA находит и устраняет такие дубликаты, создавая САМЫЙ компактный автомат для данного языка. И результат единственный - как отпечаток пальца языка.

• **Компиляторы** (gcc, clang, javac): лексический анализатор использует минимизированный DFA - меньше памяти, быстрее токенизация
• **Сетевые фильтры** (Snort, Suricata): DFA для обнаружения вторжений минимизируются, чтобы обрабатывать трафик в реальном времени
• **Верификация протоколов:** сравнение двух моделей = минимизация DFA + проверка изоморфизма

Эквивалентные состояния

Представьте карту метро, где две станции ведут к одним и тем же пунктам назначения по одинаковым маршрутам. Зачем держать обе? Одну можно убрать, объединив пассажиропотоки. Именно это делает минимизация DFA - находит **неразличимые** состояния и склеивает их.

**Определение:** Два состояния q₁ и q₂ называются **эквивалентными** (q₁ ≡ q₂), если для ЛЮБОЙ строки w ∈ Σ* автомат, стартуя из q₁, принимает w тогда и только тогда, когда стартуя из q₂ тоже принимает w. Иначе говоря - ни одна строка в мире не может их различить.

Подумайте об этом так: вы стоите в городе на перекрёстке. Ваш друг - на другом перекрёстке. Если из обоих перекрёстков любая последовательность поворотов «налево/направо» приведёт к одинаковому результату (попадёте в аэропорт или нет), значит эти перекрёстки **неразличимы**. Город можно упростить, объединив их в один.

Ключевое наблюдение: проверить ВСЕ строки невозможно - их бесконечно много. Нужен систематический подход. Вместо прямой проверки эквивалентности мы будем искать **различимые** пары - те, для которых СУЩЕСТВУЕТ строка, разделяющая их.

Наивный перебор строк НЕ доказывает эквивалентность - он лишь не нашёл контрпример. Для точного ответа нужен алгоритм table-filling, который мы разберём далее.

Алгоритм заполнения таблицы (Moore)

Алгоритм заполнения таблицы - это элегантный метод нахождения ВСЕХ различимых пар состояний. Идея проста: начнём с пар, которые **точно различимы** (accept vs reject), и будем распространять различимость «назад по переходам».

**Алгоритм Moore (table-filling):** 1. Создай таблицу для всех пар (qᵢ, qⱼ) где i < j 2. **База:** пометь как различимые все пары, где одно состояние принимающее, другое нет 3. **Итерация:** для каждой непомеченной пары (qᵢ, qⱼ) и каждого символа a ∈ Σ: если пара (δ(qᵢ,a), δ(qⱼ,a)) уже помечена как различимая → пометь (qᵢ, qⱼ) 4. **Повторяй** шаг 3, пока не прекратятся изменения 5. Непомеченные пары - **эквивалентные** состояния

Разберём на конкретном примере. Возьмём DFA, распознающий строки, где количество символов 'a' кратно 3:

**Шаг 1 (база):** Помечаем пары accept/reject: (q0,q1)×, (q0,q2)×, (q1,q3)×, (q2,q3)×, (q3,q4)×, (q0,q4)×

Сложность алгоритма Moore: O(n² · |Σ|) на каждую итерацию, до n итераций → **O(n³ · |Σ|)** в худшем случае. Для маленьких автоматов это приемлемо, но для больших есть алгоритм Хопкрофта.

Алгоритм Хопкрофта

Алгоритм Хопкрофта - это «спринтер» среди алгоритмов минимизации. Если table-filling работает O(n³), то Хопкрофт справляется за **O(n log n)** - разница как между пузырьковой сортировкой и quicksort.

**Идея алгоритма Хопкрофта:** Вместо поиска различимых ПАР, мы разбиваем множество состояний на КЛАССЫ эквивалентности. Начинаем с грубого разбиения {F, Q\F} и последовательно уточняем его, разделяя классы по переходам.

Почему добавляем в W **меньший** из двух? Это ключевая оптимизация Хопкрофта. Каждое состояние может быть «обработано» не более O(log n) раз, потому что каждый раз размер класса уменьшается как минимум вдвое. Отсюда и O(n log n).

Единственность минимального DFA

Самый красивый результат всей теории автоматов: минимальный DFA для данного регулярного языка **единственный** (с точностью до переименования состояний). Это значит: неважно, какой DFA вы начали минимизировать - результат всегда один и тот же.

**Теорема (Myhill-Nerode):** Для любого регулярного языка L существует единственный (с точностью до изоморфизма) минимальный DFA, распознающий L. Число состояний этого DFA равно числу классов эквивалентности отношения Myhill-Nerode.

Что такое отношение Myhill-Nerode? Две строки x и y **эквивалентны по Myhill-Nerode** (x ≡_L y), если для ЛЮБОГО суффикса z: xz ∈ L ⟺ yz ∈ L. Проще говоря - если x и y невозможно различить никаким «хвостом».

Единственность минимального DFA даёт нам мощный инструмент: **проверку эквивалентности регулярных языков**. Хотите узнать, задают ли два регулярных выражения один и тот же язык? Постройте DFA для каждого, минимизируйте и сравните!

**Практическое применение:** компиляторы минимизируют DFA лексического анализатора, чтобы уменьшить размер таблицы переходов. Меньше состояний → меньше памяти → быстрее лексический анализ. Инструменты вроде `flex` делают это автоматически.

Ключевые идеи

• **Эквивалентные состояния** - те, которые не может различить ни одна строка. Их можно объединить без потери информации
• **Table-filling (Moore)** - O(n³): помечаем различимые пары, начиная с accept/reject, распространяя назад по переходам
• **Хопкрофт** - O(n log n): разбиваем множество состояний на классы, уточняя разбиение по переходам. Добавляем меньший класс в рабочий список
• **Минимальный DFA единственный** - это каноническая форма регулярного языка. Два regex задают один язык ⟺ их минимальные DFA изоморфны

Связанные темы

Минимизация DFA связана с рядом ключевых тем в теории формальных языков и компиляторов:

• Конвертация NFA → DFA — Subset construction может создать экспоненциально больший DFA - минимизация уменьшает его обратно
• Регулярные выражения → автоматы — Полный пайплайн: regex → NFA → DFA → min DFA

Вопросы для размышления

• Почему нельзя минимизировать NFA тем же способом, что и DFA? Что ломается?
• Если минимальный DFA единственный, значит ли это, что минимальный NFA тоже единственный?
• Компилятор `flex` сначала строит NFA, потом DFA, потом минимизирует. Почему бы не минимизировать NFA напрямую?

Связанные уроки

• fl-08-nfa-to-dfa — Minimization is applied to DFAs, often after NFA conversion
• fl-06-dfa — Must understand DFA semantics to reason about equivalence
• fl-11-pumping-lemma — Minimal DFA characterises the language uniquely - useful for proving non-regularity
• comp-09-lexer-generators — Tools minimise DFAs to speed up generated lexers