Nondeterministic Finite Automata
Learn about nondeterministic finite automata through several examples.
Introducing nondeterminism
Consider the language , which contains strings with a in the third-to-last position. We can write it as
It will require a lot of effort to make a DFA that accepts the language . It is possible, however, to more succinctly express the idea of āends with a 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.