Chapter 9: Turing Machines and Linear Bounded Automata J;! 303
(9.12)
q: q4$ ---7 q:q4
q:q4 ---7 q4
(D) The LBA productions are
q:q.($ ---7 q4$,
$q4$ ---7 q4$,
Oq4$ ---7 q4$,
1q4$ ---7 q4$
Step 2 The productions of the generative grammar are obtained by reversing
the arrows of productions given by (9.5)-(9.12).
9.11 SUPPLEMENTARY EXAMPLES
EXAMPLE 9.13
Design a TM that copies strings of l·s.
Solution
\Ve design a TM so that we have ww after copying W E {I}*. Define M by
M = ({qa. CJI, CJ2' CJ3}' {l}. {L b}, 8. CJa, b, {q3})
where 8 is defined by Table 9.11.
TABLE 9.11 Transition Table for Example 9.13
Present state
Tape symbol
b
a
qo
qoaR
q,bL
q,
q,1L
q3bR
q2 1R
q2
q2 1R
q1 1L
q3
Tne procedure is simple.
M replaces every 1 by the symbol a. Then M replaces the lightmost a by
1. It goes to the light end of the string and writes a 1 there. Thus M has added
a 1 for the rightmost 1 in the input string w. This process can be repeated.
M reaches CJI after replacing aU1's by a's and reading the blank at the end
of the input string. After replacing a by 1. M reaches q2' M reaches q3 at the
end of the process and halts. If H' = Iii. than we have 1
211 at the end of the
computation. A sample computation is given below.
qa Il r- aqa 1 1-- aaqab r- aqja
r- a1qc.b r- aCJ I11 r- qIa11
r- 1qc. 11 r- 11CJc. 1 r- 111qc.b
r- 11CJc. 11 r- 1q I 111
r- q I 111I r- q 1 b1111 r- q3 1111