Finite-State Machines and Pushdown Automata - Models of Computation: Exploring the Power of Computing - page 175

4.7.3 A State Minimization Algorithm
The above approach does not offer a direct way to find a minimal-state machine. In this sec-
tion we give a procedure for this purpose. Given a regular language, we construct an NFSM
that recognizes it (Theorem 4.4.1 ) and then convert the NFSM to an equivalent DFSM (The-
orem 4.2.1 ). Once we have such a DFSM M , we give a procedure to minimize the number of
states based on combining equivalence classes of the right-invariant equivalence relation R M
that are indistinguishable. (These equivalence classes are sets of states of M .) The resulting
machine is isomorphic to M L , the minimal-state machine.

DEFINITION 4.7.7 Let M =(Σ , Q , δ , s , F ) be a DFSM. The equivalence relation ≡ n on states
in Q is defined as follows: two states p and q of M are n -indistinguishable (denoted p

≡ n q )if

Σ ∗ of length

and only if for all input strings u ∈

| u |≤ n either both δ ( p , u ) and δ ( q , u ) are in

F or both are not in F .(Wewrite p ≡ n q if p and q are not n -indistinguishable.) Two states p

and q are equivalent (denoted p

≡ q )if theyare n -indistinguishable for all n ≥

0 .

For arbitrary states q 1 , q 2 ,and q 3 ,if q 1 and q 2 are n -indistinguishable and q 2 and q 3 are
n -indistinguishable, then q 1 and q 3 are n -indistinguishable. Thus, all three states are in the
same set of the partition and ≡ n is an equivalence relation. By an extension of this type of

reasoning to all values of n , it is also clear that

≡ is an equivalence relation.

The following lemma establishes that ≡ j + 1 refines ≡ j and that for some k and all j ≥ k ,

≡ j is identical to ≡ k , which is in turn equal to ≡ .

LEMMA 4.7.1 Let M =(Σ , Q , δ , s , F ) be an arbitrary DFSM. Over the set Q the equivalence
relation

≡ n + 1 is a refinement of the relation ≡ n . Furthermore, if for some k ≤| Q |− ≡ k + 1

2 ,

and ≡ k are equal, then so are ≡ j + 1 and ≡ j for all j ≥ k .Inparticular, ≡ k and ≡ are identical.

Proof If p ≡ n + 1 q then p ≡ n q by definition. Thus, for n ≥ 0 ≡ n + 1 refines ≡ n .

We now show that if ≡ k + 1 and ≡ k are equal, then ≡ j + 1 and ≡ j are equal for all j ≥ k.

Suppose not. Let l be the smallest value of j for which ≡ j + 2 and

≡ j + 1 are not equal. It follows that there exist two states p and q that are indistinguishable
for input strings of length l + 1 or less but are distinguishable for some input string v of
length

≡ j + 1 and ≡ j are equal but

= l + 1. Since δ ( p , v )= δ ( δ ( p , a ) , u )
and δ ( q , v )= δ ( δ ( q , a ) , u ) , it follows that the states δ ( p , a ) and δ ( q , a ) are distinguishable
by some string u of length l + 1 but not by any string of length l . But this contradicts the
assumption that

| v |

= l + 2. Let v = a u where a

∈ | u |

Σ and

≡ l + 1 and ≡ l are equal.

≡ 0 has two equivalence classes, the final states and all other states. For each

The relation

integer j

≤ k ,where k is the smallest integer such that ≡ k + 1 and ≡ k are equal, ≡ j has at

≡ j− 1 . That is, it has at least j + 2 classes. Since

least one more equivalence class than does

≡ k can have at most | Q |

equivalence classes, it follows that k + 2

≤| Q |

.

≡ k and ≡

are identical because if two states cannot be distinguished by input
strings of length k or less, they cannot be distinguished by input strings of any length.

Clearly,

The proof of this lemma provides an algorithm to compute the equivalence relation ≡ ,

namely, compute the relations ≡ j ,0 ≤ j ≤| Q |− 2 in succession until we find two relations

that are identical. We find ≡ j + 1 from ≡ j as follows: for every pair of states ( p , q )inan

equivalence class of ≡ j , we find their successor states δ ( p , a ) and δ ( q , a ) under input letter

a for each such letter. If for all letters a , δ ( p , a )

≡ j + 1 q
because we cannot distinguish between p and q on inputs of length j + 1 or less. Thus, the

≡ j δ ( q , a ) and p ≡ j q ,then p