Недетерминированный конечный автомат

---

Недетерминированный конечный автомат (НКА, англ. nondeterministic finite automaton, NFA) — это детерминированный конечный автомат (ДКА, англ. deterministic finite automaton, DFA), который не выполняет следующие условия:

Используя алгоритм конструкции подмножеств^[англ.], любой НКА можно преобразовать в эквивалентный ДКА, то есть ДКА, распознающий тот же самый формальный язык^[1]. Подобно ДКА, НКА распознаёт только регулярные языки.

НКА предложили в 1959 году Михаэль О. Рабин и Дана Скотт^[2], которые показали его эквивалентность ДКА. НКА используется в реализации регулярных выражений — построение Томпсона^[англ.] является алгоритмом для преобразования регулярного выражения в НКА, который может эффективно распознавать шаблон строк. Обратно, алгоритм Клини^[англ.] можно использовать для преобразования НКА в регулярное выражение, размер которого в общем случае экспоненциально зависит от размера автомата.

НКА обобщён многими путями, например: недетерминированным конечным автоматом с ε-переходами, преобразователями с конечным числом состояний, автоматами с магазинной памятью, альтернирующими автоматами, ω-автоматами и вероятностными автоматами. Кроме ДКА известны другие специальные случаи НКА — однозначные конечные автоматы^[англ.] (англ. unambiguous finite automata, UFA) и самопроверочные конечные автоматы^[англ.] (англ. self-verifying finite automata, SVFA).

НКА формально представляется как 5-кортеж ${\displaystyle (Q,\Sigma ,\Delta ,q_{0},F)}$, состоящий из:

Здесь ${\displaystyle P(Q)}$ означает степень множества ${\displaystyle Q}$.

---