Problem Solving in Automata, Languages, and Complexity

270 COMPUTABILITY THEORY

(d) For some odd i, 0 < i < nz, the ith c-block x and the (i + l)st c-block

y of x do not satisfy ZR FM y.

(e) x has an odd number of c-blocks and the last c-block x of x is not a final

configuration.

(f) x has an even number of c-blocks and the last c-block ~xf of x is not the

reversal of a final configuration.

We will show that, for each of the above conditions, the set of strings satisfying

the condition is context-free and so the set of illegal computations, the union

of these sets, is also context-free.

First note that the strings of the form (5.2) are those in

and hence form a regular set. Similarly, the set of strings of the form (5.3) is

also a regular set. So, the set S1 of strings satisfying condition (a) is regular.

For condition (b), we note that the initial configurations are those of the

form (1110(10+)*110110”111) and form a regular set. (Recall that O3 repre-

sents the blank B.) So, the set of strings of the form 111OyO111, with y having

no substring 111, which are not initial configurations is also a regular set. Let

Rz be a regular expression for this set. Then, the set & of strings satisfying

condition (b) is Rz(O U l)* and, hence, is regular.

Next, we construct a PDA A&, to accept strings satisfying condition (c).

The PDA Ml works like a PDA that recognizes the set {icy 1 X, y E

{a, b)*, x # yR). We only present a sketch of Ml and leave the details as

an exercise:

(1) It nondeterministically skips through an even number of substrings

1111110 to find the beginning of a configuration u (or, just find the

beginning of the first configuration u).

(2) It reads the configuration u and stores its successor configuration z1 in

the stack. (If u does not have a successor configuration, then Ml rejects

the input .)

(3) It reads the next c-block zu of z and compares it with the string v in the

stack and accepts the input x if w # wR.

Thus, the set S3 of strings satisfying condition (c) is context-free.

Condition (d) is similar to condition (c) and we can prove, in a similar way,

that the set S4 of all strings satisfying (d) is context-free.

For condition (e), we assume that the final state of M is qh. Then, a

configuration x is a final configuration if it is in

(lllO(0 u l)llOhll(O u l)lll).

Therefore, the set of strings of the form 1110y0111, with y having no substring

111, that do not represent a final configuration is also regular. Let R5 be the