4.4.2 Testing Equivalence of Regular Languages

The table-filfing algorithm gives us an easy way to test if two regular languages are the same. Suppose languages L aud M are each represented in some way, e.g., one by a regular expression and one by an NFA. Convert eacji representation to a DFA. Now, imagine one DFA whose states are the union of the states of the DFAs for L and M. Technically; this DFA has two start states, but actually the start state is irrelevant as far as testing state equivalence is concerned, so make any state the lone start state.

Now, test if the start states of the two original DF.\s are equivalent, using the table-filhng algorithm. If they are equivalent, then L - M, and if not, then L Ф M.

Theorem 4.20: If two states are not distinguished by the table-filling algorithm, then the states are equivalent.

PROOF: Let us again assume we are talking of the DFA A - (Q,T S,gQ,F). Suppose the theorem is false; that is, there is at least one pair of states {p,q} sudi that

1. States p and q are distinguishable, in the sense that there is some string w such that exactly one of S{p, w) and S{q, w) is accepting, and yet

2. The table-filling algorithm does not find p and q to be distinguished.

Call such a pair of states a bad pair.

If there are bad pairs, then there must bo some that are distinguished by the shortest strings among all those strings that distinguish bad pairs. Let {p, q} be one such bad pair, and let w = а be a string as short as any that distinguishes p from g. Then exactly one oi6(p,w) aud S{q,w) is accepting.

Obser\-e first that to camiot be e, since if e distinguislies a pair of states, then that pair is marked by the basis part of the table-filling algorithm. Thus, n > 1.

ConsideJ the states г = 6(j).ai) and s = S{q.,ui). States r and s aie distinguished by the string aa-j since this string takes r and s to the states S{p, w) and 5{q,w]. However, the string distinguishing г from s is shorter than any string that distinguishes a bad ргиг. Thus, {r. s} cannot be a bad pair. Rather, the table-filling algorithm must have discovered that they are distinguishable.

But the inductive part of the table-filling algorithm will not stop until it has also inferred that p and q are distinguishable, since it finds that S{p.ai) r is distinguishable from 6{q,a-i) = ,s. We have contradicted our assumption that bad pairs exist. If there are no bad pairs, then every pair of distinguishable states is distinguished by the table-filling algorithm, and the theorem is true. □

CHAPTER 4. PROPERTIES OF REGULAR LANGUAGES 0 I

Start

Start

Figure 4,10: Two equivalent DFAs

Example 4.21: Consider the two DFAs in Fig, 4.10, Each DFA accepts the empty string and all strings that end in 0; that is the language of regular expression e + (0 + 1)*0. We can imagine that Fig. 4,10 represents a single DFA, with five states A through E. If we apply the table-filling algorithm to that automaton, the result is as shown in Fig. 4,11,

В С D E

A В С D

Figure 4,11: The table of distinguishabilities for Fig. 4.10

To see how the table is filled out, we start by placing xs in all pairs of states where exactly one of the states is accepting. It turns out that there is no more to do. The four remaining pairs, {Л, C}, [A.D], {C, D}, and {B,E} are all equivalent pairs. You should check that no more distinguishable pairs are discovered in the inductive part of the table-filling algorithm. For instance, with tire table as in Fig. 4,11, we cannot distinguish the pair {A, D} because on 0 they go to themselves, and on 1 they go to the pair {B, E}, which has

not yet been distinguished. Since A and С are found equivalent by this test, and those states were the start states of the two original automata, we conclude that thcse DFAs do accept the same language. □

The time to fill out the table, and thus to decide whether two states are equivident is polynomial in the number of states. If there are n states, then there are ( ), or n(n - l)/2 pairs of states. In one round, we consider all pairs of states, to see if one of their successor pairs has been found distinguishabh;, so a round surely takes no more than 0{n) time. Moreover, if on some round, no additional xs are placed in the table, then the algorithm ends. Thus, there can be no more than O(n) rounds, and 0(n) is surely an upper bound on the running time of the table-filling algorithm.

However, a more careful algorithm can fill the table in 0{n) time. The idea is to initialize, for each pair of states {r, .)}, a list of those pairs {p, q} that depiiud on {? , }. That is, if {r,s} is found distinguishable, then {p.q} is distinguishable. We create the lists initiaily by examining each pair of states {p, (j), and for each of the fixed nuniber of input symbols n. we put {p, 7} on the list for the pair of states {S{p,a),e{q,d)}, which are the successor states for p and q on input a.

If we ever find {r,s] to be distinguishable, then we go down the list for {r.s}. For each pair on that list that is not already distinguishable, we make that pair distinguishable, and wc put the pair on a queue of pairs whose lists we must dieck sinularh-.

The total work of this algorithm is proportional to the sum of the lengths of the lists, since we are at all times either adding something to the lists {initialization) or examining a member of the list for the first and last time {when we go down the list for a pair that has been found distinguishable). Since the size of the input alphabet is considered a constant, each pair of states is put on 0(1) lists. As there are 0{n) pairs, the total work is O(n).

4.4.3 Minimization of DFAs

Anotlier important consequence of the test for equi\alence of states is that we can minimize DFAs. That is, for each DFA we can find an equivalent DFA that has as few states a-s any DFA accepting the same language. Moreover, except for our ability to call the states by whatever names we choose, this minimum-state DFA is unique for the language. The algorithm is as follows:

1. First, eliminate any state that cannot be reached from the start state.

2. Then, partition the remaining states into blocks, so that all states in the same block are ecjuivalent., and no pair of states from different blocks are equivakint. Theorem 4.24, below, shows that we can always make such a partition.

Example 4,22: Consider the table of Fig. 4.9, where we determined the state equivalences and distinguishabilities for the states of Fig. 4.8. The partition