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.