nondeterministic finite automaton

A nondeterministic finite state automaton is a tuple A = <Q, Sigma, Delta, q₀, F >, where Q, Sigma, q₀ and F are as in the definition of deterministic finite state automata, and Delta ⊆ Q x (Sigma u e) x Q is a transition relation; here; e (sometimes denoted as Lambda) is the special empty string symbol.

That is, in each state we may have not exactly one transition defined on each symbol, plus we may also have empty transitions, ie. transitions that change the state without reading a symbol at all.

Alternatively, these automata can be defined to have just a single accepting state, or not to have any, but instead to accept when the automaton would block.

Or nondeterministic finite automata, uses the logic of the finite automata combined with nondeterminism. Nondeterminism is a generalization of determinism, so every deterministic finite automaton is automatically a nondeterministic finite automaton. The difference between the DFA and the NFA lies in the transition function. An NFA is allowed to have zero, one, or many exiting arrows for each alphabet symbol.

So, how does an NFA compute, then? Whenever the NFA is presented with multiple paths to take for its specified inputs, it "splits off into copies" of itself. For an NFA with three states (q1, q2, q3), if the transition between q1 and q2 is 1, and the transition between q1 and q3 is also 1, then the NFA splits into two copies, one which reads the next input from state q2, the other reads its input from state q3. At the end of the string, if any of the copies of the NFA are in an acceptance state, the NFA will accept the string.

Similar to the above example, e-transitions cause NFA splits as well. If any NFAs are in acceptance states, or states that can reach acceptance states via e-transitions when the string is terminated, then the NFA accepts the string.

See also: DFA, finite automata