Introducing nondeterminism

Consider the language KK, which contains strings with a 11 in the third-to-last position. We can write it as K={all strings of 0’s and 1’s ending with 100,101,110, or 111}.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 KK. It is possible, however, to more succinctly express the idea of “ends with a 11 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.

Get hands-on with 1200+ tech skills courses.