Problem Solving in Automata, Languages, and Complexity

2.7 Minimum Deterministic Finite Automata 71

symbol, Z.XN E L e yw E L for all w E (0 + l)+. Moreover, since x and y also
end with the same symbol, x E L H y E L. Therefore, for any w E (0 + l)*,
xw E L ( yw E L. That is, xR~y.
From the above characterization of the relation RL, we can easily see that
RL has five equivalence classes:

[&]RL = 6

PI RL = 0 + o(0 + 1>*0, PI RL = 1+ l(0 + 1)*1,

WI RL = o(o + l)*l, PO1 RL = l(0 + l)*o.^0

The following lemma relates, for a regular language L, Index(RI;) with the

number of states in a DFA A4 that accepts L.

Lemma 2.47 Assume that L is accepted by a DFA A4 = (Q, C, s, S, F).

Then, for any strings x, y E C*, if 6(s, x) = S(s, y) then x RL y.

Proof. Suppose that S(s,x) = S(s,y) in M. Then, for any w E C*,

6(s, xw) = s(s(s, x), w)) = qs(s, Y), w)) = J(s, YW)*

Therefore, for any w E C*, xw E L if and only if yw E L. Cl

The above lemma shows that if L is accepted by a DFA A4 of n states,
then all strings with the same ending state are in the same equivalence class
of RL. Therefore, Index(RL) is bounded by n and is finite. Thus, if we can
find a DFA accepting language L with exactly Index(RL) states, then this
DFA must be a minimum DFA. The following theorem shows that, in fact,
this property characterizes the minimum DFA’s.

Theorem 2.48 For any regular language L, its minimum DFA has exactly
Index( RL) states.

Proof. Assume that L is a language over alphabet C. Define a DFA A4 =
(Q, C, 8, s, F) as follows:

(1) Q = {[~]RL 1 x E c”);

(2) ~([~]RLY a) = [X&L;

(3) = [&]RL;

(4) “F = {[x]RLIx E L}*

From the discussion above, we know that if L is regular then Index(RL) < 00.
It follows that Q is a finite set. In addition, the function S is well defined
because

[~]RL = [Y~L = [=&L = [yah~

= +]R,,a) = [xa]R, = [YU]RL = @]Rr.&+