Конвертация NFA → DFA: Subset Construction

NFA - элегантный инструмент для описания паттернов: ветвления, ε-переходы, параллельные пути. Но компьютер не умеет «угадывать» правильный путь. Ему нужен DFA - единственный переход из каждого состояния. Как автоматически превратить свободу NFA в точность DFA? Алгоритм subset construction - мост между проектированием и реализацией.

• **Компиляторы и grep:** регулярное выражение → NFA (просто построить) → DFA (быстро исполнить). Это происходит при каждом `grep` в терминале.
• **Сетевые IDS (Snort, Suricata):** тысячи паттернов атак объединяются в один NFA, затем конвертируются в DFA для проверки трафика со скоростью линка.
• **Лексический анализ:** токенизатор в вашем любимом языке программирования использует DFA, построенный из NFA для всех токенов.

Алгоритм построения подмножеств

NFA - мощный инструмент проектирования. Но **компьютеру нужен DFA**, потому что в каждый момент он должен точно знать, в каком состоянии находится. Как превратить NFA (с недетерминизмом и параллельными путями) в DFA?

Идея гениальна: **DFA симулирует ВСЕ параллельные пути NFA одновременно**. Каждое состояние DFA - это множество состояний NFA, в которых NFA мог бы находиться после прочтения входа.

**Аналогия:** представьте детектива, который отслеживает подозреваемого в лабиринте с развилками. NFA - подозреваемый выбирает путь случайно. DFA - детектив ставит камеры на ВСЕХ возможных развилках и отслеживает ВСЕ варианты сразу.

Алгоритм **Subset Construction** (построение подмножеств) работает пошагово:

1. Начальное состояние DFA = {начальное состояние NFA} (+ ε-замыкание)
2. Для каждого нового состояния DFA и каждого символа алфавита - вычислить переход: объединение всех переходов NFA из каждого состояния множества
3. Если полученное множество - новое, добавить как новое состояние DFA
4. Повторять, пока не перестанут появляться новые состояния
5. Принимающие состояния DFA = все множества, содержащие хотя бы одно принимающее состояние NFA

**frozenset** в Python - неизменяемое множество, которое можно использовать как ключ словаря. Идеально для представления состояний DFA, ведь каждое из них - множество.

ε-замыкание: невидимые переходы

Прежде чем применять subset construction, нужно разобраться с **ε-переходами** - переходами, которые NFA делает «бесплатно», без чтения символа.

**ε-замыкание (ECLOSE)** состояния q - это множество ВСЕХ состояний, достижимых из q по цепочке ε-переходов (включая само q).

**Аналогия:** ε-переходы - как эскалаторы в аэропорту. Вы можете бесплатно «перетечь» через них без посадочного талона (символа). ECLOSE - все залы, в которые вы попадёте, пользуясь только эскалаторами.

Для вычисления ECLOSE используем обход графа - BFS или DFS. Идём по всем ε-рёбрам из заданного множества состояний, пока не перестанем находить новые.

**Частая ошибка:** забывают включить само состояние q в ECLOSE(q). По определению, q всегда достижимо из самого себя по нулю ε-переходов.

Полный пример: NFA → DFA шаг за шагом

Разберём полный пример конвертации. Возьмём NFA, распознающий строки, содержащие подстроку **"ab"**:

Применяем **subset construction**. Начальное состояние DFA - {q0}. Для каждого множества вычисляем переходы по 'a' и 'b':

**Проверка:** DFA должен принимать ровно те строки, что и NFA. Протестируйте на "ab" (принять), "ba" (отклонить), "aab" (принять), "bab" (принять).

Экспоненциальный взрыв: 2ⁿ состояний

NFA с n состояниями может породить DFA с **до 2ⁿ состояниями** - каждое подмножество из n элементов может стать отдельным состоянием DFA. Это не теоретическая абстракция - существуют NFA, где взрыв происходит на практике.

Классический пример: язык **"n-й символ с конца - 1"** над алфавитом {0, 1}. NFA для этого языка элементарен, но DFA неизбежно большой.

**4 состояния NFA → 8 состояний DFA.** В общем случае: NFA для «n-й символ с конца = 1» имеет n+1 состояний, а минимальный DFA - ровно 2ⁿ. Это доказуемый нижний предел.

На практике экспоненциальный взрыв - скорее исключение. Большинство NFA из реальных задач порождают DFA с гораздо меньшим числом состояний, потому что не все подмножества достижимы.

**Lazy evaluation (ленивое построение)** - оптимизация для больших NFA. Вместо построения всего DFA заранее, состояния создаются **по мере необходимости** при обработке входной строки.

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

• **Subset construction** превращает NFA с n состояниями в эквивалентный DFA, где каждое состояние DFA - подмножество состояний NFA.
• **ε-замыкание (ECLOSE)** - множество состояний, достижимых по ε-переходам. Это первый шаг перед любым переходом.
• **Экспоненциальный взрыв** возможен (до 2ⁿ), но на практике большинство подмножеств недостижимы.
• **Lazy evaluation** - создавать состояния DFA по требованию, а не все сразу. Ключевая оптимизация для больших NFA.

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

Конвертация NFA → DFA - центральное звено в цепочке: regex → NFA → DFA → минимальный DFA.

• NFA: недетерминированные автоматы — Входные данные для subset construction
• Regex ↔ автоматы — Regex → NFA (Thompson) → DFA (subset) - полный pipeline
• Минимизация DFA — После конвертации DFA можно минимизировать (алгоритм Хопкрофта)

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

• Почему NFA удобнее для проектирования, а DFA - для исполнения? В каких задачах вам пригодился бы каждый из них?
• Если lazy DFA кеширует вычисленные состояния, то при достаточно длинном входе он фактически построит полный DFA. Есть ли способ ограничить размер кеша?
• Можно ли использовать subset construction для конвертации NFA с бесконечным алфавитом? Что изменится?

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

• fl-07-nfa — Must understand NFA before converting it
• fl-06-dfa — Conversion target - DFA semantics must be clear
• fl-10-dfa-minimization — After conversion, minimize the resulting DFA
• comp-09-lexer-generators — Lexer generators apply subset construction internally
• comp-07-regex-in-lexer