78 FINITE AUTOMATA
is not regular.
Example 2.54 Show that the following language is not regular:
L = {XP I x E {O,l)‘)*
Proof. For any x:, y E Ol with x # y, we know that zzR E L and y# 4 L.
Thus, any two different strings in 0 1 must belong to two different equivalence
classes of RL. This means that Index(RL) = 00. Thus, by Corollary 2.49, L
is not regular. cl
Example 2.55 Show thut L = {Omln 1 gcd(m, n) = 1) is not regular.
Proof. For any two different primes p and q, OP 1P @ L and OQ 1P E L. There-
fore, OJ’ and 09 are not in the same equivalence class of RL. Since there are an
infinite number of primes, we have Index(RL) = 00. Thus, L is not regular.
0- Example 2.56 For any language L, define an equivalence relation DL by
x DL y # (Vu) (VW) [uxw E L e uyw E L].
Show that L is regular if and only if Index(DL) < 00.
Proof. Clearly, for any strings x and y, x DL y implies x RL y. Thus,
Index( RL) < - Index( DL). It follows that Index(DL) < 00 implies that L
is regular.
Conversely, assume that L is regular. To show that Index(DL) < 00, we
consider a DFA M = (Q, C, 6, qo, F) accepting L and define an equivalence
relation DM on C* as follows:x DM y e (Vqi E Q) [s(4i, x) = s(qi, y)l-
First, note that x DM y implies x DL y. It follows that Index(DL) < -
Index( DM). A ssume that the state set Q of M is {qo,ql,.. .,q+l}. We
claim that DM has at most nn equivalence classes. To see this, we observe
that every equivalence class [x]D~ can be represented in the following way:[X]DM = nfil{Y 1 Q&,x) = ~(4ilYb
i=o
That is, [x]~~ is uniquely determined by the following sequence of n states:&Z = (S(q0,X),6(ql,X),..*,6(Qn-11x))*If two strings x and y have the same sequence Qz = &, then x DM y. Thus,
the number of equivalence classes of the relation DM is the number of possible
sequences Qz, which is bounded by nn. Therefore, we have Index(DL) <
Index(DM) < nn - < 00.^0