286 ~ Theory of Computer Science
(b) The rightmost 1 is found and replaced by a blank b.
(c) The RJW head returns to the starting position.
A computation is illustrated in Table 9.4.
TABLE 9.4 Computation for 11 h111
q o 11b111 f- 1q o 1b111 f- 11q o b111 f- 111q1 111
f- 1111q1 11 f- 11111q1 1 f- 111111q1 b f- 11111q21b
f- 1111 q31 bb f- 111 q311 bb f- 11 q3111 bb f- 1q31111 bb
f- q311111bb f- q3b11111bb f- bq f 11111bb
From the above computation sequence for the input string 11b11 L we can
construct the transition table given in Table 9.5.
For the input string Ibl, the computation sequence is given as
q o lblI-lq o bl 1- llql 1 1- 11lqj b r- 11 q2b r- 1 q3 1bb
r- q3 11bb r- q3b Ilbb r- bq f l1bb.
TABLE 9.5 Transition Table for Example 9.6
Present state
Tape symbof
b
---'fqo
1Rqo
1Rq1
q1
1Rq1
bLq2
q2
bLq3
q3
1Lq3
bRqf
@
EXAMPLE 9.7
Design a TM that accepts
{O"I"ln 2: l}.
Solution
We require the following moves:
(a) If the leftmost symbol in the given input string IV is 0, replace it by x
and move right till we encounter a leftmost 1 in ).i'. Change it to y and
move backwards.
(b) Repeat (a) with the leftmost O. If we move back and forth and no 0 or
1 remains. move to a final state.
(c) For strings not in the form 0"1", the resulting state has to be nonfinal.