Недетерминированные автоматы (NFA)

Каждый раз, когда вы пишете регулярное выражение вроде `.*error.*timeout.*`, движок regex создаёт недетерминированный автомат, который параллельно исследует ВСЕ способы сопоставить паттерн с текстом. NFA - это автомат-«ясновидящий»: он умеет угадывать правильный путь. И парадокс - этот трюк с угадыванием не даёт ему никакой дополнительной мощности по сравнению с обычным DFA.

• **Регулярные выражения** - каждый regex компилируется в NFA (алгоритм Томпсона), который потом может быть преобразован в DFA для быстрого сопоставления
• **Лексеры компиляторов** - flex, re2c объединяют сотни правил через ε-переходы в один NFA, затем конвертируют в DFA
• **Сетевое сканирование** - Snort IDS использует NFA-based pattern matching для обнаружения угроз в реальном времени

Недетерминизм: несколько путей сразу

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

В DFA функция перехода δ(q, σ) возвращает **одно** состояние. В NFA - **множество** состояний. Из состояния q0 по символу '1' автомат может перейти и в q0, и в q1, и в q2 - все три пути исследуются параллельно.

**NFA принимает строку, если ХОТЯ БЫ ОДИН путь приводит в принимающее состояние.** Не все пути, не большинство - достаточно одного.

Сравним DFA и NFA для одной задачи: **принять строки, заканчивающиеся на "01"**.

NFA проще для проектирования: вместо продумывания всех переходов мы описываем только «удачный путь». Автомат сам исследует все варианты.

Как это работает для строки "1001"? Автомат в q0 читает '1' - остаётся в q0 (0,1-петля). Читает '0' - **раздваивается**: один клон остаётся в q0, другой идёт в q1. Клон в q0 читает '0' - снова два клона. Клон в q1 читает '0' - нет перехода, **этот клон умирает**. В итоге один из клонов проходит q0→q1→q2 по последним символам "01" и оказывается в принимающем.

NFA - это **не** случайный выбор пути! Это параллельное исследование ВСЕХ путей. Если хоть один путь ведёт к принятию - строка принята.

ε-переходы: спонтанные скачки

NFA может делать переходы **без чтения символа** - это ε-переходы (эпсилон-переходы). Автомат спонтанно перемещается между состояниями, не потребляя вход.

Зачем? Главная причина - **склейка автоматов**. Если у нас есть NFA для языка L₁ и NFA для L₂, мы можем построить NFA для L₁ ∪ L₂ (объединение) или L₁ · L₂ (конкатенация) простой «проводкой» через ε-переходы.

**ε-замыкание (ε-closure)** - множество всех состояний, достижимых из данного по цепочке ε-переходов. Это ключевое понятие для алгоритма превращения NFA в DFA (следующий урок).

Когда NFA с ε-переходами запускается, стартовое множество - не {q₀}, а **ε-closure(q₀)**. Автомат уже в старте может «разветвиться» по всем ε-достижимым состояниям.

ε-переходы - синтаксический сахар. Они не добавляют NFA мощности (распознают те же языки), но колоссально упрощают конструкции. Именно так работает алгоритм Томпсона для компиляции regex → NFA.

NFA на практике: три примера

Построим три NFA, где недетерминизм делает конструкцию значительно проще, чем DFA.

Пример 1: Строки, содержащие "101"

**Задача:** принять строки из {0, 1}*, содержащие подстроку "101" где угодно.

Обратите внимание: в DFA нужно аккуратно обработать частичные совпадения ("10" → потом '1' → снова начинаем "101"). NFA просто запускает новые «клоны» на каждой единице.

Пример 2: Третий символ с конца - '1'

**Задача:** принять строки из {0, 1}*, где третий символ с конца - '1'. Например: "100", "1101", "01011**1**00".

Этот NFA имеет всего **4 состояния**. Эквивалентный DFA потребует **8 состояний** (2³ = 8) - нужно помнить последние 3 символа. Это первый намёк на экспоненциальный разрыв!

Пример 3: Делится на 2 ИЛИ на 3

**Задача:** принять бинарные числа, которые делятся на 2 **или** на 3. Мы уже строили отдельные DFA для каждого условия - теперь соединим их через ε.

Модульная склейка через ε - мощный инженерный приём. В лексерах компиляторов сотни правил (число, строка, ключевое слово...) объединяются через ε в один NFA, который затем конвертируется в DFA.

Мощность NFA: компактность и эквивалентность

Вот главный вопрос: NFA допускает недетерминизм - может ли он распознать БОЛЬШЕ языков, чем DFA? Ответ удивителен.

**Теорема (Рабин-Скотт, 1959):** Класс языков, распознаваемых NFA, совпадает с классом языков, распознаваемых DFA. Это - класс регулярных языков.

Доказательство конструктивное: для любого NFA с n состояниями можно построить эквивалентный DFA методом **subset construction** (подмножеств). Каждое состояние DFA - это МНОЖЕСТВО состояний NFA. Детали - в следующем уроке.

Но если мощность одинакова, зачем NFA? Ответ: **компактность**. NFA может быть ЭКСПОНЕНЦИАЛЬНО меньше эквивалентного DFA.

Экспоненциальный разрыв: n-й символ с конца

Задача: «n-й символ с конца = 1» для произвольного n.

NFA требует **n + 1** состояние (линейно). DFA требует **2ⁿ** состояний (экспоненциально). При n = 30 NFA имеет 31 состояние, а DFA - больше миллиарда. Это не теоретический курьёз - это реальное ограничение.

Обратите внимание на метод `accepts`: вместо одного состояния мы храним **множество** текущих состояний. На каждом шаге для каждого состояния из множества вычисляем все переходы, объединяем, добавляем ε-замыкание. Это и есть симуляция недетерминизма.

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

• **NFA допускает несколько переходов** из одного состояния по одному символу - автомат исследует все пути параллельно
• **ε-переходы** - спонтанные переходы без чтения символа, используются для модульной склейки автоматов
• **NFA = DFA по мощности** - оба распознают ровно класс регулярных языков (теорема Рабина-Скотта)
• **NFA компактнее DFA** - экспоненциальный разрыв: NFA с n+1 состояниями может требовать DFA с 2ⁿ состояниями
• **Симуляция NFA** - через множества текущих состояний за O(m · n) вместо построения экспоненциального DFA

Связь с другими темами

NFA - мост между регулярными выражениями и эффективной реализацией:

• DFA - детерминированные автоматы — NFA и DFA эквивалентны по мощности, но NFA может быть экспоненциально компактнее
• Конвертация NFA → DFA — Алгоритм subset construction превращает NFA в эквивалентный DFA
• Регулярные выражения → автоматы — Алгоритм Томпсона строит NFA из regex, используя ε-переходы для union, concat, star

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

• NFA не добавляет мощности конечным автоматам. А что насчёт более мощных моделей - добавляет ли недетерминизм мощность автоматам с магазинной памятью (PDA)?
• Симуляция NFA через множества состояний занимает O(m·n) времени. Конвертация в DFA даёт O(m), но может потребовать 2ⁿ памяти. Когда каждый подход предпочтительнее?
• Если NFA для задачи «n-й символ с конца = 1» имеет n+1 состояние, а DFA - 2ⁿ, то сколько состояний у DFA для задачи «n-й И m-й символы с конца = 1»?

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

• fl-06-dfa — NFA is understood by contrast with DFA
• fl-08-nfa-to-dfa — Subset construction makes NFA practically usable
• fl-09-regex-to-automata — Thompson construction builds NFA from regex
• fl-05-regex — NFA is the natural compilation target for regex
• comp-06-lexer-basics