Problem Solving in Automata, Languages, and Complexity

30 FINITE AUTOMATA

0 a

0 C

Figure 2.9: Solution to Example 2.8.

Suppose that the string ~1~2 •GC~ is stored on the tape, where each pi

denotes one bit in (0, 1). Th en, we may check each of the substrings ~1~2,

X2X3,.... Xn- 1~~ in turn, to see whether it is equal to 00, and accept the

input string as soon as a substring 00 is found. This suggests the following

way to construct the required DFA.

Step 1. Build a checker as shown in Figure 2.9(a), with state q2 being a

success state, meaning that if two consecutive O’s are found then the input

string is to be accepted. In particular, if ~1x2 = 00, the the string x is

accepted.

Step 2. If x1 = 1, then we give up on substring ~1x2 and continue to check

~2x3. So, we need to go back to state ~0; that is, d(qo, 1) = qo. This action is

shown in Figure 2.9(b).

Step 3. If xl = 0 and x2 = 1, then neither ~1x2 nor ~2x3 is 00. So, we also

need to go back to restart at qo to check x3x4. That is, we let S(al, 1) = qo.

Figure 2.9(c) shows the complete DFA. cl

In general, suppose that ~1x2 l l l X~ is the string on the tape and we want

to check xl... xk, x2.. l xk+l,... , xn-k+i l l l X~ in turn to match a substring

ala2°00ak. Then, we set up k + 1 states qo, 41,... , qk, with qi standing for

“found ala2... a$’ At state qi, if b = ai+l, then we define s((li, b) = qi+l. If

b # ai+l, then we define J(qi,b) = qj, where j is the maximum index j such

that

That is, we find the longest suffix y of al l l l sib which is a prefix of al l l l ak

and go to qlvl. The following example explains this idea more clearly.

Example 2.9 The set of all binary strings having the substring 00101.

Solution. Following the above idea, we first construct a checker as shown in

Figure 2.10(a).