288 g Theory of Computer Science
Solution
Before designing the required Turing machine M, let us evolve a procedure for
processing the input stJing 112233. After processing, we require the ID to be
of the form bbbbbbq;. The processing is done by using five steps:
Step 1 qj is the initial state. The RJW head scans the leftmost 1, replaces 1
by b, and moves to the right. M enters q2'
Step 2 On scanning the leftmost 2, the RJW head replaces 2 by b and moves
to the right. M enters q3'
Step 3 On scanning the leftmost 3. the RJW head replaces 3 by b, and moves
to the right. M enters q4'
Step 4 After scanning the rightmost 3, the RJW heads moves to the left until
it finds the leftmost 1. As a result. the leftmost 1. 2 and 3 are replaced by b.
Step 5 Steps 1-4 are repeated until alll's, 2's and 3's are replaced by blanks.
The change of IDs due to processing of 112233 is given as
qj 112233 1- bq212233 1- blq22233 1- blbq3233 1- blb2q3 33
r- blb2bq..j31- blb 2 qsb3 1- b1bq s 2b3 1- b1qsb2b3 1- bq s 1b2b3
r- q6b1b2b31- bq]lb2b31- bbq2b2b3 1- bbbq22b3
r- bbbbq3b3 1- bbbbbq3 3 1- bbbbbbq..jb r- bbbbbq;bb
Thus.
q\112233 ~ q7bbbbbb
As q7 is an accepting state, the input string 112233 is accepted.
Now we can construct the transition table for M. It is given in Table 9.6.
TABLE 9.6 Transition Table for Example 9.7
Present state
Input tape symbol
2
3
b
-'>q.,
bRq2
q2
1Rq2
bRq3
q3
2Rq3
bRq4
q4
3Lqs
qs
1Lqa
2Lqs
qs
1Lqs
(~
bRq1
bRq2
bRq3
bLq7
bLQs
bRQ1
It can be seen from the table that strings other than those of the form 0"1"2"
are not accepted. It is advisable to compute the computation sequence for
strings like 1223, 1123. 1233 and then see that these strings are rejected by M.