Minimal Automata

DFAs are useful in recognizing text patterns and are easily implemented in code. We haven’t considered, however, whether an automaton is “efficient.” Our measure of efficiency is the number of states, since that determines the number of possible transitions that exist.

Making DFA efficient

Let’s examine the following DFA, $D_e$, for any redundant states.