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.

Once we reach state $q_2$, the machine remains in an accepting state regardless of subsequent input. States $q_2$ and $q_3$ can therefore collapse into a single accepting state, as shown in the figure below.

Now let’s think about what language the machine above accepts. If a string starts with a $b$, it is accepted. If it starts with an $a$, it is not accepted until a $b$ is read. In other words, this machine accepts the language of strings that have at least one $b$. We can therefore combine states $q_0$ and $q_1$ to obtain the minimal DFA in the figure below.

We’ve discovered that states $q_0$ and $q_1$ play the same role in the original DFA ($D_e$). States $q_2$ and $q_3$ are likewise indistinguishable in their function, and we have reduced the number of states from 4 to 2.

Identifying distinguishable states

Which states are indistinguishable in the DFA $D_a$ ...