176 TURING MACHINES(3) Sequences S and T are consistent sequences in QR, because S(p, 0) =(Q, 0, R) and So amd Tl are consistent (from rule (iii)).
From the above recursive definition of consistent sequences, we can con-
struct the NFA M’ as A4’ = (&R, {o,l),s',((s,R)),((h,R))), where 6' is de-
fined as follows: For each state Sr E QR and each input a E C,
aJ’(s~,u) = {Sz E QR I SI + 5'217
and for each state S1 E QR,
S’(SI,E) = (5’2 E QR 1 5’1 G S2).
To see that L(A4’) = L(M), first assume that M accepts an input z. Also
assume that in the computation of A4 on X, the rightmost cell it ever visits
is Cm, and that it halts at cell Cj, 1 < J’ < m. in state h. Without loss of
generality, we may assume that m > - 1~3. Then, the computation path of A4
corresponds to a sequence of crossing sequences So, Sr ,... , Sm, that has the
following properties:
(a) So = ((s, R)). (Note: The tape head of A4 cannot move over the left
boundary of Co.)
(b) For each 0 < - i < - m - 1, Si 2 ,$+I, where zi is the ith symbol of input
x: if 1 < - i < - n, and pi = B otherwise.(c) (/z, R) occurs as the last pair in Sj.
Now, from property (c) and rules (i), (ii) and (iii), we know that (h, R) occurs
as the last pair in each Si, for j < i < nz. (Note: If (h, R) is in S and S $ T
for some a, then (h, R) must occur - T in T.) Furthermore, we know, from rule
(i), that Sm $ ,!&+I, where Sm+r = ((h, R)). So, the computation path of
A&’ that guesses the states So, Sr,... , Sm+r will accept input X.
Conversely, if A&’ accepts the input X, then the sequence of states So, Sr ,... 7 S m+i, where vz > - 1x1, must have the properties (a), (b) above, plus
(c’) sm+1 = ((h R))*
From these crossing sequences, we can reconstruct the computation pathof A4 on IX: as follows: First, we change each pair (4, R) in S;, 0 < - i < - m. + 1,
to the configurationx~.qx~x~+l l l l G-n+1>,
where xi is the ith symbol of input x if 1 < i < n, and xi = B, otherwise.
(Note: This configuration contains extra trailing blank symbols B.) Also,