Nondeterministic Finite Automata

Introducing nondeterminism

Consider the language $K$, which contains strings with a $1$ in the third-to-last position. We can write it as $K = \{ \textrm{all strings of } 0 \textrm{'s and } 1 \textrm{'s ending with } 100,\:101,\:110, \textrm{ or } 111 \}.$

It will require a lot of effort to make a DFA that accepts the language $K$. It is possible, however, to more succinctly express the idea of “ends with a $1$ in the third-to-last position” than a DFA allows. With nondeterminism, we can get right to the point of expressing exactly what we want, as shown in the nondeterministic finite automaton (NFA) in the following figure.