= Nondeterministic finite automaton
{wiki}
= NFA
{c}
{synonym}
A <nondeterministic finite automaton> allows a <set> of possible destinations for each <automaton state> and input symbol. Without the extra moves permitted in an <Epsilon-NFA>, replace the <DFA> <function> by $\Delta:Q\times\Sigma\to\mathcal P(Q)$, where $\mathcal P(Q)$ is the <power set>. A <word> is accepted when at least one path consumes all its symbols and ends in an accepting <automaton state>. These choices express <existential quantification>, not <probability>: no chance of choosing a particular path is assigned. One successful path suffices even if other paths fail.
Consider a three-state <NFA> accepting exactly the <words> of <binary digits> ending in $01$. Its initial <automaton state> $q_0$ loops on both $0$ and $1$; it also has an <automaton transition> $q_0\xrightarrow{0}q_1$, followed by $q_1\xrightarrow{1}q_2$. Only $q_2$ is accepting, and all unlisted <automaton transitions> are absent. Staying at $q_0$ skips an arbitrary beginning; leaving it guesses that the current zero starts the final two symbols.
\Image[/nondeterministic-suffix-traces.png]
{title=An <NFA> recognizing <words> ending in $01$, and the possible <automaton states> after each symbol}
The <word> $01$ accepts along $q_0\to q_1\to q_2$. The <word> $1101$ accepts along $q_0\to q_0\to q_0\to q_1\to q_2$. The <word> $010$ rejects: a path reaching $q_2$ after $01$ cannot consume the remaining zero, while the other paths end outside $q_2$. Thus finding $01$ somewhere is insufficient; it must occur at the end.
To simulate the <NFA> deterministically, retain the <set> $S$ of all currently possible <automaton states>. The <powerset construction> updates $S$ by taking the <union> of the destinations of its members. Here only $\{q_0\}$, $\{q_0,q_1\}$, and $\{q_0,q_2\}$ are reachable, although the full <power set> has eight members. Reading $010$ gives $\{q_0\}\to\{q_0,q_1\}\to\{q_0,q_2\}\to\{q_0,q_1\}$, which rejects. In general, an $N$-state <NFA> yields a <DFA> with at most $2^N$ <automaton states>. Nondeterminism can simplify a description, while the <powerset construction> keeps the memory finite.
The second generator checks all 511 <words> of up to eight <binary digits> against the direct test of whether their final two symbols are $01$. Exactly 127 accept, and only the three listed <sets> of <automaton states> occur. In particular, the <empty word> rejects for this <NFA>.
Michael O. Rabin and Dana Scott's 1959 paper studied <finite-state machines> as recognizers with finite internal memory. Its section 5 defines <NFAs> through successful paths, and theorem 11 proves their equivalence to <DFAs> by the <powerset construction>. This gives a historical source for the distinction between many possible paths and greater recognition power: https://www.cs.cmu.edu/~lblum/flac/Handouts_pdf/rs.pdf[Rabin and Scott, Finite Automata and Their Decision Problems, pp. 120–121]{ref}.
Back to article page
