Minimization of Dfas

CIS 262 Fall 2015: Minimization of DFAs

This handout explains the algorithm for minimizing a DFA. Given a DFA A = (Q;; q0; F; ), we want to

construct a DFA B such that (1) both DFAs A and B accept exactly the same language, and (2) the DFA

B has as few states as possible. The algorithm proceeds in three steps: remove unreachable states, compute

equivalent states, and merge equivalent states.

Step 1: Removing Unreachable States

A state q of a DFA A is said to be reachable if there is a path from the initial state to the state q by following a

sequence of transitions. That is, q is reachable i there exists a string w such that (q0;w) = q. It is easy to

see that unreachable states are redundant, and can be removed without changing the language that the DFA

accepts. When we construct a DFA manually, there is no reason to include unreachable states, but when

a DFA is constructed by an algorithm (for instance, by the determinization algorithm for translating NFAs

to DFAs), it may contain unreachable states. If the DFA is represented by listing its states and transitions,

then the set of reachable states of a DFA can be computed using an algorithm for searching in graphs (for

example, the depth-rst-search algorithm).

Henceforth, we will assume that the set Q of states contains only reachable states.

Step 2: Computation of Equivalent States

Dene two states q and q0 to be equivalent if for all strings w, the states (q;w) and (q0;w) are either

both accepting or both non-accepting. Conversely, the states q and q0 are distinguishable if there exists a

string w such that only one of the states (q;w) and (q0;w) is accepting. Intuitively, two equivalent q and

q0 states can be merged: no matter what additional input string follows, the decision of the DFA regarding

whether to accept or reject is identical from both these states.

The algorithm below computes the set of distinguishable pairs of states:

Initialize: S := f(q; q0) j exactly one of q or q0 is in F g.

Repeat

S := S [ f(q; q0) j ((q; a); (q0; a)) 2 S for some a 2  g

Until S does not change.

The logic of the algorithm is simple: an accepting state is distinguishable from a non-accepting state, and

if we have declared two states s and s0 to be distinguishable, and there is an a-labeled transition from state

q to s, and also an a-labeled transition from state q0 to s0, then we can conclude that states q and q0 are

distinguishable. Below is the proof that this algorithm works correctly.

1. Termination: If Q contains n states, then there are only n2 pairs of states. The algorithm only adds

pairs to the set S, and stops when no new pair can be added. Thus, the loop cannot execute for more

than n2 iterations, and the algorithm must terminate.

2. We claim that if the algorithm adds a pair (q; q0) to the set S during the k-th iteration of the loop,

then the states q and q0 are distinguishable. The proof is by induction on k.

Base case, k = 0, means that the algorithm adds (q; q0) to S initially. In this case, only one of them is

accepting. Then of the two states (q; ") and (q0; "), only one is accepting, and thus, by denition

of distinguishability, the states q and q0 are distinguishable.

For inductive case, suppose that the algorithm adds (q; q0) to S during (k+1)-th iteration. Then, there

must be a symbol a such that (s; s0) is already in S, for s = (q; a) and s0 = (q0; a). Since the pair

(s; s0) is added to S during the k-th iteration or earlier, by strong induction hypothesis, states s and

s0 must be distinguishable. Thus, there must be a string w such that only one of the states (s;w)

and (s0;w) is accepting. It follows that only one of the states (q; aw) and (q0; aw) is accepting.

Hence the states q and q0 are distinguishable.

1

3. We now need to show that if two states q and q0 are distinguishable, then the algorithm adds the pair

(q; q0) to the set S.

Consider two distinguishable states q and q0. By denition, there must exist a string w such that only

one of the states (q;w) and (q0;w) is accepting. Let k be the length of shortest such string. The

claim is that the algorithm adds the pair (q; q0) to the set S during the k-th iteration of the loop. The

proof is by induction on k, and is left as an exercise.

We have not described how to eciently implement the algorithm: this amounts to choosing an appro-

priate data structure for the set S and deciding on the order in which dierent pairs should be processed

within the loop-body. We will not focus on this aspect in this course, but let us note that there is a very

nice implementation of this algorithm with running time O(n log n), where n is the number of states.

Step 3: Building Minimal DFA by Merging Equivalent States

The algorithm