Problem Solving in Automata, Languages, and Complexity

(^174) TURING MACHINES
B (^0 0 1 1) B
s-p-q-q-q-q
-J
Figure 4.10: Crossing sequences.
For this DTM A& we show in Figure 4.10 the crossing sequences of the
following computation path of M on input 0011:
(s, Booll) I- (p,B@ll) k (q, BOo11) k (q, BOOLI)
t- (q, BOOll) t-- (q, BOOllE3) t- (r, BOOIL) l- (t, Boo11) -

t- (t,BOOll) - t- (P, BOOll) - t- (p, BOOII) - l- (q, Booll) - i- - - l

In Figure 4.10, the crossing sequence between cells Ci and Ci+i is written
under the boundary between the two cells. For instance, the crossing sequence

between cells Cl and C2 is (+ q, r t, -+ p). For convenience, we write

((?I, R), (5 L), (P, R)) t o d enote this crossing sequence. Thus, the pair (q, R)

means that the tape head was moving from left to right when it crossed the
boundary and the new state after that is q.
We observe the following two properties of the crossing sequences:
(a) If a computation path of M contains a crossing sequence in which the
same pair (q, D), with q E Q, D E {L, R}, occurs twice, then this computation
path contains two identical configurations and so it is in an infinite loop and
does not accept. For instance, the crossing sequence between C2 and C’s in

Figure 4.10 is ((CL R), (6 L>, (4, R)), with two occurrences of the pair (q, R).

They correspond to
computation path,
never halts.

(b) Any two consecutive pairs (q, Di), (p, D2) in a crossing sequence must

have D1 # D2, since the tape head must move in different directions in two

the two occu rrences of the configuration (q,BOOll) in the

and indicate that t he computaion of M on input 0011

crossings over the same boundary.
Since we are only interested in the accepting paths of A& we define, for-

mally, a crossing sequence to be a finite sequence of pairs ((al, Dl), (42, Dz),

“‘I (qm, Dm)) in (Q U {h}) x {L, R}, with the properties (i) Di # Di+l for

l<i<m- 1, and (ii) (qi, Di) # (qj, Dj) for 1 < i < j < ~72.

Noi, we go back to the design of the NFA E’. The-idea of M’ is to use
the crossing sequences as the states to process the input. Assume that the

input is x, with 1x1 = n. It starts with crossing sequence So = ((s, R)) at

the left boundary of cell CO. At each step, iV’ looks at the current crossing