Введение
Тип машины конечного состояния в теории автоматов
В теории автоматов машина конечного состояния называется детерминированным конечным автоматом (DFA), если каждый её переход однозначно определяется её исходным состоянием и входным символом, и для каждого перехода состояния требуется считывание входного символа. Недетерминированный конечный автомат (NFA) или недетерминированная машина конечного состояния не обязан соблюдать эти ограничения. В частности, любой DFA также является NFA. Иногда термин NFA используется в более узком смысле, обозначая NFA, который не является DFA, но в данной статье это не так. С помощью алгоритма построения подмножеств любой NFA можно преобразовать в эквивалентный DFA, то есть DFA, распознающий тот же формальный язык. Как и DFA, NFA распознают только регулярные языки. NFA были введены в 1959 году Майклом О. Рабином и Даной Скоттом, которые также показали их эквивалентность DFA. NFA используются при реализации регулярных выражений: конструкция Томпсона — это алгоритм компиляции регулярного выражения в NFA, который может эффективно выполнять сопоставление с образцом в строках. Обратно, алгоритм Клине может быть использован для преобразования NFA в регулярное выражение (размер которого обычно экспоненциально зависит от размера входного автомата). NFA были обобщены различными способами, например, недетерминированные конечные автоматы с ε-переходами, конечные преобразователи, автоматы с магазинной памятью, чередующиеся автоматы, ω-автоматы и вероятностные автоматы. Помимо DFA, другие известные частные случаи NFA — это однозначные конечные автоматы (UFA) и самопроверяющие конечные автоматы (SVFA).
each of its transitions is uniquely determined by its source state and input symbol, and
reading an input symbol is required for each state transition. A nondeterministic finite automaton (NFA), or nondeterministic finite state machine, does not need to obey these restrictions. In particular, every DFA is also an NFA. Sometimes the term NFA is used in a narrower sense, referring to an NFA that is not a DFA, but not in this article. Using the subset construction algorithm, each NFA can be translated to an equivalent DFA; i. e., a DFA recognizing the same formal language. Like DFAs, NFAs only recognize regular languages. NFAs were introduced in 1959 by Michael O. Rabin and Dana Scott, who also showed their equivalence to DFAs. NFAs are used in the implementation of regular expressions: Thompson's construction is an algorithm for compiling a regular expression to an NFA that can efficiently perform pattern matching on strings. Conversely, Kleene's algorithm can be used to convert an NFA into a regular expression (whose size is generally exponential in the input automaton). NFAs have been generalized in multiple ways, e. g., nondeterministic finite automata with ε moves, finite state transducers, pushdown automata, alternating automata, ω automata, and probabilistic automata. Besides the DFAs, other known special cases of NFAs
are unambiguous finite automata (UFA)
and self verifying finite automata (SVFA).
Неофициальное введение
Есть два способа описать поведение НКА, и оба они эквивалентны. Первый способ использует недетерминизм, отраженный в названии НКА. Для каждого входного символа НКА переходит в новое состояние, пока не будут обработаны все входные символы. На каждом шаге автомат недетерминированно "выбирает" один из возможных переходов. Если существует хотя бы один "успешный путь", то есть некоторая последовательность выборов, приводящая к принимающему состоянию после полного потребления входной строки, строка принимается. В противном случае, то есть если ни одна последовательность выборов не может обработать всю входную строку и привести к принимающему состоянию, строка отклоняется. Второй способ заключается в том, что НКА обрабатывает входную строку символ за символом. На каждом шаге, если применимо два или более переходов, он "клонирует" себя на соответствующее количество копий, каждая из которых следует по своему переходу. Если переход не применим, текущая копия заходит в тупик и "завершается". Если после обработки всей входной строки хотя бы одна из копий находится в принимающем состоянии, строка принимается, иначе – отклоняется.
Формальное определение
Для более элементарного ознакомления с формальным определением обратитесь к теории автоматов.
Сложность
Можно решить задачу об определении пустоты для НКА за линейное время, то есть проверить, пуст ли язык заданного НКА. Для этого можно просто выполнить поиск в глубину, начиная с начального состояния, и проверить, достижима ли какая-либо конечная конфигурация. Проверка, является ли заданный НКА универсальным, то есть существует ли строка, которую он не принимает, является задачей, полной по классу сложности PSPACE. Как следствие, то же самое верно и для задачи включения, то есть, заданы два НКА, является ли язык одного подмножеством языка другого. Заданы НКА A и целое число n, задача подсчета количества слов длины n, принимаемых A, является неразрешимой; она является #P-трудной. Фактически, эта задача является полной (при экономных сведениях) для класса сложности SpanL.
Применение NFA
NFA и DFA эквивалентны: если язык распознается NFA, то он также распознается DFA, и наоборот. Установление этой эквивалентности важно и полезно. Это полезно, поскольку построение NFA для распознавания заданного языка иногда значительно проще, чем построение DFA для этого же языка. Это важно, потому что NFA позволяют упростить математические выкладки, необходимые для доказательства многих важных свойств в теории вычислений. Например, доказывать свойства замкнутости регулярных языков с помощью NFA гораздо легче, чем с помощью DFA.