A nondeterministic
finite state automaton is a tuple
A = <Q, Sigma, Delta, q
0, F >, where Q, Sigma, q
0 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.