of the states into equivalent blocks is {{A,E}, {B,H}, {C}, {D,F}, {G}). Notice that the three pairs of states that are equivalent are each placed in a block together, while the states that are distinguishable from all the other states are each in a block alone.

For the automaton of Fig. 4.10, the partition is {{A,C,D}.. {B,E]). This example shows that we can have more than two states in a block. It may appear fortuitous that A, C, and D can all live together in a block, because every pair of them is equivalent, and none of them is equivalent to any other state. However, as we shall see in the next theorem to be proved, this situation is guaranteed by our definition of equivalence for states. □

Theorem 4.23: The equivalence of states is transitive. That is, if in some DFA A = (Q, E,(S,(j(o, F) w-e find that states p and q are equivalent, and we also find that q and r aie equivalent, then it must be that p and г are equivalent.

PROOF: Note that transitivity is a property we expect of any relationship called equivalence. However, simply calling something equivalence doesnt make it transitive; we must prove that the name is justified.

Suppose that the pairs {p, q} and {q, r} are equivalent, but pair {p, r} is distinguishable. Then there is some input string w such that exactly one of 5{j),w) and dir,w) is an accepting state. Suppose, by symmetry, that 6{p,w) is the accepting state.

Now consider whether S(q,w) is accepting or not. If it is accepting, then {q,r} is distinguishable, since 5(q,w} is accepting, and 5{t,w) is not. if 6{q,ic) is nonaccepting, tlien {p, q) is distinguishable for a similar reason. We conclude by contradiction that {р,т} was not distinguishable, and therefore this pair is equivalent. □

We can use Theorem 4.23 to justify the obvious algorithm for partitioning states. For each state q, construct a block that consists of q and all the states that are equivalent to q. We must show that the resulting blocks are a partition; that is, no state is in two distinct blocks.

First, observe that all states in any block are mutually equivalent. That is, if p and г are two states in the block of states equivalent to q, then p and r are equivalent to each other, by Theorem 4.23.

Suppose that there are two overlapping, but not identical blocks. That is, tliere is a block Б that includes states p and g, and another block С that includes p but not q. Since p and q are in a block together, they are equivalent. Consider how the block С was formed. If it was the block generated by p, then q would be in C, because those states are equivalent. Thus, it must be that there is some third state s that generated block C; i.e., С is the set of states equivalent to a.

We know that p is equialent to s, because p is in block C. We also know that p is equivalent to q because they are together in block B. By the transitivity of Theorem 4.23, q is equivalent to s. Bnt then q belongs in block C, a contradiction. We conclude that equivalence of states partitions the states; that is, tw-o

states either have the same set of eqiii*alent states (inelyding themselves), or their equivalent states are disjoint. To conclude the above analysis:

Theorem 4.24: If we create for each state g of a DFA a block consisting of q and all the states equivalent to q, then the different blocks of states form a partition of the set of states. That is, each state is in exactly one block. All members of a block are equivalent, and no pair of states chosen from different blocks are equivalent. □

We are now able to state succinctly the algorithm for minimizing a DFA A = ((3,E,(J,9o,F).

1. Use the table-filling algorithm to find all the pairs of equivalent states.

2. Partition the set of states Q into blocks of mutually equivalent states by the method described above.

3. Construct the mininmm-state equivalent DFA В by using the blocks as its states. Let 7 be the transition function of B. Suppose 5 is a set of equivalent states of A, imd a is an input symbol. Thou there must exist one block T of states such that for all states q in S, 5{(j: a) is a member of ЪЪск Т. For if not, then input symbol a takes two states p and g of 5 to states in different blocks, and those states are distinguishable by Theorem 4.24. That fact lets us conclude that p and q are not equival(!nt, and they did not both belong in S. As a consequence, we can let 7(6, й) = Т. In addition:

(a) The start state of В is the block containing the start state of .4.

(b) The set of accepting states of В is the set of blocks containing accepting states of A. Note that if one state of a block is accepting, then all the states of that block must be acceptuig. The reason is that any accepting state is distinguishable from any nonaccepting state, so you cant have both accepting and nonaccepting states in one block of equivalent states.

Example 4.25: Let us minimize the DFA from Fig. 4.8. We established the blocks of the state partition in Example 4.22. Figure 4.12 sliows the minimum-state automaton. Its five states correspond to the five blocks of equivalent states for the automaton of Fig. 4.8.

The start state is {A,E}, since A was the start state of Fig. 4.8. The only accepting state is {C}, since С is the only accepting state of Fig. 4.8. Notice that the transitions of Fig. 4,12 properly reflect the transitions of Fig, 4.8. For instance, Fig. 4.12 has a transition on input 0 from {A,E} to Б,Я}. That

You should remember that the иате block may be formed several times, starting from different states. However, the partition consists of thfi diffcrani blocks, so thi.s block арреаг.ч only once in tluj partition.

Start

Figure 4,12: Minimum-state DFA equivalent to Fig. 4.8

nialces sense, because in Fig. 4.8, A goes to В on input 0, and E goes to H. Likewise, on input 1, {A.E} goes to {D,F}. If we examine Fig. 4.8, we find tliat both A and F go to F on input 1, so the selection of the successor of {A, E] on input 1 is also correct. Note that the fact neither A nor E goes to D oil input 1 is not important. You may check that all of the other transitions are also proper. □

4.4.4 Why the Minimized DFA Cant Be Beaten

Suppose we have a DFA A, and we minimize it to construct a DFA M, using the partitioning method of Theorem 4.24. That theorem shows that we cant group the states of A into fewer groups and stiU have an equivalent DFA. However, could there be another DFA Л, unrelated to A, that accepts the same language as A and M, yet has fewer states than M? We can prove by contradiction that does not exist.

First, run the state-distinguishabifity process of Section 4.4.1 on the states of M and iV together, as if they were one DFA. We may assume that the states of M and N have no names in common, so the transition function of the combined automaton is the union of the transition rules of M and N, with no interaction. States are accepting in the combined DFA if and only if they are accepting in the DFA from which they come.

The start states of M and N are indistinguishable because L{M) - L{N). Further, if {p, q} are indistinguishable, then their successors on any one input