DFA minimisation

By minimising an automaton we mean finding an equivalent automaton with the smallest possible number of states. Even an automaton with no redundant state can still be simplified further.

Example

Let us take this automaton:

The automaton accepts only the strings 01 and 11. It is clear that there is a simpler automaton with three states that accepts the same language. The states q₁ and q₂ can be merged into one new state {q₁, q₂}; the transitions that led into q₁ or q₂ will lead into the new state, and the same goes for the transitions leaving q₁ and q₂. We get this automaton:

This automaton clearly accepts the same language as the previous one and has fewer states.

Equivalence of states

Let A = ⟨Q, Σ, δ, q₀, F⟩ be an automaton. We define the language of a state q ∈ Q, written L(q), as

$L (q) = L (⟨ Q, Σ, δ, q, F ⟩)$

That is, we change the start state of the automaton A from q₀ to q and work out the language accepted by this automaton. In other words, the language L(q) contains all strings w such that in the automaton A we get from the state q to an accepting state on reading w. Going back 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 q₁, q₂ are equivalent states and we make each of them the start state of the automaton, they generate the same language. In other words: if the automaton reaches the configurations ⟨q₁, w⟩ and ⟨q₂, w⟩, then it must either accept in both cases or reject in both cases.

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

Minimising an automaton is therefore about finding equivalent states and removing them by merging them into one new state, just as we did in the example above.

How to find equivalent states

Which states are certainly not equivalent? An accepting state and a non-accepting state are certainly not equivalent, because the language of an accepting state differs from the language of a non-accepting state: an accepting state certainly accepts the string ε, a non-accepting one does not. We will show the procedure straight away on an example. Let us take this automaton:

We start by creating two sets of states

$\begin{array}{rcl} S_{1} & = & F = {q_{3}, q_{6}}, \\ S_{2} & = & Q ∖ F = {q_{0}, q_{1}, q_{2}, q_{4}, q_{5}} . \end{array}$

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

$\begin{array}{ccccc} group & state & 0 & 1 \\ S_{1} & q_{3} & q_{5} & q_{4} \\ q_{6} & — & — \\ 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 change the table so that, instead of writing directly which states we go to for a given symbol, we note only the group we move into. For example, from the state q₃ on reading 0 we get to the state q₅, which is in the group S₂. So instead of q₅ we write S₂ in the table:

$\begin{array}{ccccc} group & state & 0 & 1 \\ S_{1} & q_{3} & S_{2} & S_{2} \\ q_{6} & — & — \\ 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}$

Next we split both groups. We always put into the same group the states that move into the same groups for all symbols. For example, the states q₃ and q₆ will not be in the same group, because for neither 0 nor 1 do they go into the same group. On the other hand, the states q₁ and q₂ will be in the same group, because neither has a transition for 0 and both go into the group S₁ for 1. This creates the new groups:

$\begin{array}{ccccc} group & state & 0 & 1 \\ q_{3} & S_{2} & S_{2} \\ q_{6} & — & — \\ q_{0} & S_{2} & S_{2} \\ q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ q_{4} & S_{1} & — \\ q_{5} & S_{1} & — \end{array}$

In every group the states have the same transitions. We label the newly created groups and again find out which of these new groups the states lead into:

$\begin{array}{ccccc} group & state & 0 & 1 \\ S_{1} & q_{3} & S_{5} & S_{5} \\ S_{2} & q_{6} & — & — \\ S_{3} & q_{0} & S_{4} & S_{4} \\ S_{4} & q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ S_{5} & q_{4} & S_{2} & — \\ q_{5} & S_{2} & — \end{array}$

At this point we split the groups again. But we see that no further split is possible, as we would get the same groups: the states q₁ and q₂ do have the same transitions between groups, but they are already in the same group and there is no other state in the group S₄. The algorithm for finding equivalent states is finished. From each group it is enough to pick one state; we delete the others, and all transitions that led into deleted states will lead into the one state we picked.

So we can choose that our new automaton has the states q₃, q₆, q₀, q₁, q₄, and we remove the states q₂ and q₅. All transitions that led into q₂ now lead into q₁, and all transitions that led into q₅ lead into q₄:

Procedure for minimising an automaton

Remove the unreachable states,
remove the redundant states,
remove the equivalent states.

Sources

Chapters: Unreachable states, Redundant states, DFA minimisation

« Previous: Redundant states

Next: Closure properties of regular languages »