Minimizing the automaton

By minimizing an automaton, we mean finding an equivalent automaton that contains the minimum possible number of states. Even an automaton that contains no redundant state can be further simplified.

Example

Consider the following automaton:

The automaton accepts only the words 01 and 11. It is obvious that there is a simpler automaton with three states that accepts the same language. The states q₁ and q₂ can be combined into one new state {q₁, q₂} and those transitions that led to the states q₁ or q₂ will lead to the new state, and the same for transitions coming from q₁ and q₂. We get this automaton:

This automaton apparently accepts the same language as the previous one while having fewer states.

Equivalence of states

Consider the automaton $A=\left<Q, \Sigma, \delta, q_0, F\right>$. We define the language of the state q∈ Q, denoting L(q) as

$$ L(q) = L(\left<Q, \Sigma, \delta, q, F\right>) $$

That is, we change the initial state of the automaton A from q₀ to q and compute the language accepted by this automaton. In other words, in the language L(q), all words w are such that we get from the state q for the word w to the end state of the automaton A. Returning to the previous automaton, L(q₁) = {1}.

We say that two different states q₁ and q₂ are equivalent if

$$ L(q_1) = L(q_2) $$

What does this mean? If the states of q₁, q₂ are equivalent, then if we make them the initial states of the automaton, they will generate the same language. In other words, if the automaton gets to the configurations <q₁, w> and <q₂, w>, it must either accept or reject in both cases.

Going back to the previous automaton: the states q₁ and q₂ are equivalent, because if we are in the state q₁, we can only accept the input word if the unread part of the word is equal to 1. Same if we are in the state q₂.

Thus, minimizing the automaton is about finding equivalent states and removing these states by merging them into a new state, just as we did in the example above.

How to find equivalent states

What states will certainly not be equivalent? If we take an end state and a non-end state, they will certainly not be equivalent, because the language of the end state is different from that of the non-end state - the end state certainly accepts the word $\varepsilon$, the non-end state does not. We'll show the procedure right away with an example. So let's have this automaton:

We start by creating two sets of states

\begin{eqnarray} S_1&=&F=\left\{q_3, q_6\right},\ S_2&=&Q\setminus F=\left\{q_0, q_1, q_2, q_4, q_5\right}. \end{eqnarray}

Now we create a transition table and keep the information about the groups S₁ and S₂:

$$ \begin{array}{c|c|cc|c} \mbox{ Group }&\mbox{ Status }&0&1\\\hline S_1&q_3&q_5&q_4\\ &q_6&—&—\\\hline S_2&q_0&q_1&q_2\\ &q_1&—&q_3\\ &q_2&—&q_3\\ &q_4&q_6&—\\ &q_5&q_6&—\\ \end{array} $$

Now we modify the table so that instead of having the table directly say what states it goes to for a given symbol, we just note the group we are transitioning to. For example, from the state q₃ for 0 we go to the state q₅, which is in the group S₂. So instead of q₅ we write S₂ in the table:

$$ \begin{array}{c|c|cc|c} \mbox{ Group }&\mbox{ Status }&0&1\\\hline S_1&q_3&S_2&S_2\\ &q_6&—&—\\\hline S_2&q_0&S_2&S_2\\ &q_1&—&S_1\\ &q_2&—&S_1\\ &q_4&S_1&—\\ &q_5&S_1&—\\ \end{array} $$

Now we further split the two groups. We always put the states that go into the same groups for all symbols. For example, the states q₃ and q₆ will not be in the same group, because neither for 0 nor for 1 go into the same group. Conversely, the states q₁ and q₂ will be in the same group because both states do not transition for 0 and both states go to the group S₁ for 1. This creates new groups:

$$ \begin{array}{c|c|cc|c} \mbox{ Group }&\mbox{ Status }&0&1\\\hline &q_3&S_2&S_2\\\hline &q_6&—&—\\\hline &q_0&S_2&S_2\\\hline &q_1&—&S_1\\ &q_2&—&S_1\\\hline &q_4&S_1&—\\ &q_5&S_1&—\\ \end{array} $$

We have the same transitions in each group. We mark the newly created groups and again find out which of these new groups the states go to:

$$ \begin{array}{c|c|cc|c} \mbox{ Group }&\mbox{ Status }&0&1\\\hline S_1&q_3&S_5&S_5\\\hline S_2&q_6&—&—\\\hline S_3&q_0&S_4&S_4\\\hline S_4&q_1&—&S_1\\ &q_2&—&S_1\\\hline S_5&q_4&S_2&—\\ &q_5&S_2&—\\ \end{array} $$

At this point, we make another splitting of the groups. But we can see that we can't do any more splitting, we would get the same groups - because the states q₁ and q₂ have the same transitions within the groups, but they are already in the same group and there is no more state in the group S₄. The algorithm for finding equivalent states is finished. We just need to select one state from each group, delete the others, and all the states that led to the deleted states will lead to the one state we selected.

Thus, we can choose to have our new automaton have the states q₃, q₆, q₀, q₁, q₄ and delete the states q₂ and q₅. All transitions that led to q₂ will now lead to q₁ and all states that led to q₅ will lead to q₄:

Automata minimization procedure

1. Remove unreachable states,
2. remove redundant states,
3. remove equivalent states.

Sources

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools
• Minimization of automata [PDF]