Nondeterministic finite automaton

Remarks

Example: over $\Sigma = \set{a, b}$, take $Q = \set{0, 1, 2}$, $q_0 = 0$, $F = \set{2}$, $\Delta(0, a) = \set{0, 1}$, $\Delta(0, b) = \set{0}$, $\Delta(1, a) = \Delta(1, b) = \set{2}$ and $\Delta(2, a) = \Delta(2, b) = \emptyset$. A run ends in state $2$ exactly when it moves to state $1$ on the second-to-last letter, and that letter is $a$. So $L(N)$ is the set of words whose second-to-last letter is $a$. Non-example: an automaton with a transition that reads no symbol, an $\varepsilon$-move, is not an NFA in this sense, because $\Delta$ is only defined on $Q \times \Sigma$; it is an $\varepsilon$-NFA. A DFA $(Q, \Sigma, \delta, q_0, F)$ is the NFA with $\Delta(q, a) = \set{\delta(q, a)}$. Some authors allow a set of initial states instead of a single one; this does not change the class of accepted languages.