Minimization of DFAs

Let M be a DFA and q be a state of M. Let L(q) be the language accepted by the DFA obtained from M by making q the start state. Now two states q and r of M are called equivalent iff L(q)=L(r).

Non-equivalence of states can be established inductively as follows:

a final state is not equivalent to a non-final state (Why?)
if a is in the alphabet and delta(q,a) is not equivalent to delta(r,a) then q is not equivalent to r. (Why?)

If two states cannot be proven non-equivalent by means of the two rules above, they must be equivalent. (Why?)

If a DFA has two equivalent states we may erase one of them and redirect all transitions leading to the erased state to the other one. This will not affect the language recognized by the DFA.

Easy question (for exam?): Why not?

In this way a DFA can be converted into one in which no two different states are equivalent.

Another way to make a DFA smaller (having less states) is to erase useless states; states that are not reachable from the start state by means of any input string.

A DFA is called minimal if there is no smaller DFA accepting the same language. Any DFA can be minimized by eliminating useless states and reducing equivalent states until there is only one state left in every equivalence class. This results in a minimal DFA: there is no DFA accepting the same language which has even fewer states. It can be shown that the minimal DFA accepting a given language is unique (up to the naming of states).

Rob van Glabbeek

rvg@cs.stanford.edu