Problem Solving in Automata, Languages, and Complexity

66 FINITE AUTOMATA

Figure 2.44: A DFA over a singleton alphabet has exactly one cycle.

Proof. We prove this result in four steps. First, we consider a simple case

where A = 0* and B C - O*. Assume that B is accepted by a DFA k?~. Since

A.& operates on only one symbol 0, each state in the transition diagram of

k!~ has exactly one out-edge. It follows that the transition diagram of &

contains exactly one cycle, as shown in Figure 2.44. Suppose that this cycle

contains c edges and that the path from the initial state s to the first state p

in the cycle contains a edges, where c > 1 and a > 0. We claim that for all

integers m, with m2 > a, 0” E C(O*, B)if and only if Om+c E C(O*, B).

To prove our claim, we first note that 0” E C(O*, B) if and only if Om2 E

B, and Om+c E C( 0* , B) if and only if O(“+“J2 E B. Since m2 > - a, the

computation path of MB on input Om2 starts from the initial state s and ends

at a state q in the cycle. It is clear that, for any k 2 0, the computation path

of & on input Om2+kc also ends at state q. That is, Om2 E B if and only if

Om2+kc E B for all k - > 0. It follows that

0” E C(O, B) e Om2 E B a Om2+(2m+c)c E B o Omfc E C(O, B).

From this claim, we can construct a DFA MC accepting C(O*, B) as follows:

A&c is a single-cycle DFA as shown in Figure 2.44, with [fil edges from state

s to state p, and with c edges in the cycle. A state q is a final state if and

only if Oj2 E B where j is the number of edges in the shortest path from s to

q. This completes the proof of the first case.

Next, we consider the case where A = C* for some alphabet C and B C O*.

Using the same argument as above, we can see that IX: E C(C*, B) if andkly

if xz E C(C*, B) for all x of length 121 = c. Furthermore, 2 E C(C*, B) if

and only if w E C(C* , B) f or all strings w of length IwI = 1~1. Therefore, we

can construct A& for set C(C*, B) as in the first case above, except that we

replace each edge -% by a family of edges a\ over all symbols a E C.

In the third step, we assume that A = C* and B C I’* for some alphabets

C and l?. Let Bo = {OIXl I z E B}. We note that Bo can be obtained from B

by replacing each symbol a E C by symbol 0, and so, by Example 2.35, Bo is

regular. In addition, it is easy to verify that C(C*, Bo) = C(C*, B). It follows

from the second case that C(C* , B) is regular.

Finally, we consider the general case of A C - C* and B C - I’* for some