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.

Two things stand out in the transition graph above. First, there are two choices for transitions from the initial state for an input of the symbol $1$; we may either stay in state $0$ or move to state $1$. This is what makes this machine nondeterministic. Second, there are no out-edges exiting the accepting state. This is because we want to end there. For a string to end in the accepting state, we must choose the edge from state $0$ to state $1$ at just the right moment. If such a choice can be made, we say that the NFA accepts the string. An accepting path for the input string $10110$ is the sequence of states $0,0,0,1,1?,1??$. Clearly, only strings with a $1$ in the correct position can end in the final state. The important thing here is how much easier it is to conceive and express a NFA for this language than a DFA.

This may seem a strange approach to designing finite automata, and programming such a machine may appear to require some sort of backtracking procedure, in case we don’t make the right choice (because we don’t know ahead of time when an input symbol is the last one in the string). Alas, we can’t “back up” in a finite automaton; all decisions must be made based only on the current state and input symbol. Fortunately, it is possible to convert any NFA to a DFA by keeping track of all possible moves as we go. Let’s see some more NFAs.

NFA accepting strings that begin and end with the same symbol

The NFA in the figure below accepts a language $L$ over $\{a,b \}$, which contains strings of length two or greater that begin and end with the same symbol. We can write it as $L = \{ \textrm{all strings of length at least two that begin and end with the same symbol} \}.$

The nondeterminism occurs in the middle states, where there are two choices for $a$ and $b$ ...