72 FINKCE AUTOMATA
*
q2Figure 2.45: Computation path of a string 20.By a simple induction, we can extend this property to J([E]R~, z) = [x]~~, for
all ir: E C”. This shows that L(M) = L:
Since M has Index(&) states, it is, by Lemma 2.47, a minimum DFA for L.
Cl
Corollary 2.49 A language L is regular if and only if Index&) < 00.
Proof. Note that, in the proof of Theorem 2.48, we did not use the fact that
L is regular. That is, we can construct the minimum DFA for any language
L as long as Index(&) < 00. Thus, such languages L must be regular. 0
Example 2.50 Show that L is regular if and only if there exists a positive
integer k such that x RL y if and only if for every x E C* with 121 5 k,
x2 E L H yx E L.
Proof. First, assume that L is regular and is accepted by a DFA &? =
(Q, C,S, s, F). Let k = l&l2 - 1. We claim that if xx E L ti yx E L for all x
of length ]z] < k, then x RLY. To see this, let us consider the product DFA
M = M x AX For every string w of length lull > k, the computation path of
A& on w, starting from state qr = [S(s, x), S(s, y)] to & = [S(s, xw), S(s, yw)],
contains at least IQ]” + 1 states. Therefore, it contains some cycles in the
transition diagram of M. Let us eliminate these cycles and keep only a sim-
ple path from Q; to &. This simple path corresponds to the computation
path of M on a string x of length ]z] < k, from q; to qz. (E.g., we show in
Figure 2.45 the computation path of astring w = wlw2w3w4w5w6, with ~2,
w4 and w5 associated to the two cycles. We eliminate these cycles to form a
new string 2 = wlw3wg which is associated with the simple path.) That is,
qs = [S(s, xz), S(s, yz)]; or, S(s, xw) = S(s, xz) and 6(s, yw) = S(s, yz). Now,
by the assumption, xz E L e yx E L; that is, two states S(s, xz) and S(s, yz)
both are in F or both are not in F. Therefore, xw E L ( yw E L. It follows
that x RL y.
Conversely, suppose there exists such a constant k. Note that each x can
divide C* into at most two parts: {x I xz E L} and {x I xz 6 L}. Therefore,
RL has at most 21+lCl+“*+lClk equivalence classes. Hence, by Corollary 2.49,
L is regular. cl