Exercise 4.3.4: Give an algorithm to tell whether two regular languages L\ and L2 have at least one string in common.

Exercise 4.3.5: Give an rxlgorithm to tell, for two regular languages Li and L2 over the same alphabet Т., whether there is any string in E* that is in neither L\ nor L2.

4.4 Equivalence and Minimization of Automata

In contrast to the previous questions - emptiness and membership - whose algorithms were rather simple, the question of whether tMo descriptions of two regular languages actually define the same language involves considerable intellectual mecliariics. In this section we discuss how- to test whether two descriptors for regular languages are equivalent, in the sense that they define the same language. An important consequence of this test is that there is a way to minimize a DFA. That is, we can take any DFA and find an equivalent DFA that has the minimum number of states. In fact, this DFA is essentially unique: given any two minimum-state DF.As that are equivalent, we can always find a way to rename the states so that the two DFAs become the same.

4.4.1 Testing Equivalence of States

We shall begin by asking a question about the states of a single DFA. Our goal is to understand w-hen two distinct states p and q can be replaced by a single state that behaves like both p and q. We say that states p and 9 are equivalent if:

For all input strings w, 6{p, w) is an accepting state if and only if e{q, w) is an accepting state.

Less formally, it is impossible to tell the difference between equivalent states p and q merely by starting in one of the states and asking whether or not a given input string leads to acceptance when the automaton is started in this (unknown) state. Note we do not require that S{p, w) and S{q, -w) are the .same state, only that either both are accepting or both are nonaccepting.

If tw states are not equivalent, then we say they are distinguishable. That is, state p is distinguishable from state q if there is at least one string w such that one of Hp,w) and S{q,u}) is accepting, and the other is not accepting.

Example 4.18: Consider the DFA of Fig, 4.8, whose transition function we shall refer to as 5 in this example. Certain pairs of states are obviously not equivalent. For example, С and G are not equivalent because one is accepting and the other is not. That is, the empty string distinguishes these two states, because 5(C, e) is accepting and 6(G,e) is not.

Consider states A and G. String e doesnt distinguish them, because they are both nonaccepting states. String 0 doesnt distinguish them because they go to

4.4. EQUIVALENCE AND MINWIIZATION OF AUTOM.ATA Start

Figure 4.8: An automaton with equivalent states

states В and G, respectively on input 0, and both these states are nonaccepting. Likewise, string 1 doesnt distinguish A from G, because they go to F and E, respectively, and both are nonaccepting. However, 01 distinguishes .4 from G, because S{A, 01) - C. 5{G, 01) = B, С is accepting, and E is not. .Any input string that takes A and G to states only one of which is accepting is sufficient to prove that A and G are not equivalent.

In contrfxst, consider states A and E. Neither is accepting, so e does not distinguish them. On input 1, they both go to state F. Thus, no input string that begins with 1 can distinguish A from E, since for any string x, 6{A, Ix) = 6(E, Ix).

Now consider the behavior of states A and E on inputs that begin with 0. Tbey go to states В and Я, respectively. Since neither is accepting, struig 0 by itself does not distinguish A from E. However, Б aud H are no help. On input 1 they both go to C, and on input 0 they both go to G. Thus, all inputs that begin with 0 will fail to distinguish A from E. We conclude that no input string whatsoever will distinguish A from E; i.e., they are equivalent states. □

To find states that are equivalent, we make our best efforts to find pairs of states that are distinguishable. It is perhaps surprising, but true, that if we try our best, accorduig to the idgorithm to be described below, then any pair of states that we do not find distinguishable are equivalent. The algorithm, which we refer to as the table-filling algorithm, is a recursive discovery of distinguishable pairs in a DF.A. A - [Q, S, 5, q.F).

BASIS: If p is an accepting state aud q is nonaccepting, then the pair {pq} is distinguishable.

INDUCTION: Let p and q be states such that for some input symbol n, r -(5(p, o) and .ч - S{q, a) are a pair of states known to be distinguishable. Then

(p, q} is a pair of distinguishable states, Tho reason this rule makes sense is that there must be some .string vj that distinguishes r from в; that is, exactly one of й(г,);-) and 6{s,vi) is accepting. Then string шо must distinguish p from q, since 6{p,(iiv) and 6{q,aw) is the same pair of states as 5(r, v/j) and S{s,w).

Example 4ЛЭ: Let us execute the table-filling algorithm on the DFA of Fig 4,8. The final table is shown in Fig. 4.9, where an x indicates pairs of distinguishable states, and the blank scpiares indicate those pairs that have been found equivalent. Initially, there an* no xs in the table.

Figure 4,9: Table of state inequivalences

For the basis, since С is the only accepting state, we put xs in each pair that involves С Now that we know some distingui.shable pairs, we can discover others. For instance, since {C, Я} is distinguisliabh!, and states E <md F go to H and С respectively, on input 0, wc know that {E,F} is also a distinguishable pair. In fact, all the xs in Fig. 4.9 with the exception of the pair {.4, G] can be discovered simply by looking at the transitions from the \у<ш of states on either 0 or on 1, and observing that {for one of tiiose inputs) one state goes to С and the other does not. We can show {A,G} is distinguishable on the next round, since on input 1 they go to F and E, r(!s]>ectively, and we already established that the pair {E,F} is distinguishable.

However, theu we can discover no more distinguishable pairs. The three remaining pairs, whicli aiO tiierefore equivalent pairs, are {A,E], {В.Я}, and {D, F). For example, consider why we can not infer that {.4, E} is a distinguishable pair. On input 0, A and E go to £f and Я, respectively, and {B, H} has not yet been shown distinguishable. On input 1, A and E both go to F, so there is no hope of distinguisiiing them that way. The other two pairs, {В,Я} and {D, F) will never be distingui.shed because they each have identical transitions on 0 and identical transitions on 1, Thus, the table-filling algorithm stops with the table as shown in Fig, 4,9, which is the correct determination of equiralent and distinguishable states. □