Solutions (or Hints) to Chapter-end Exercises !;t 409
TABLE A9.1 Transition Table for Exercise 9.8
Present state
--7 qa
q1
q2
q3
q4
q5
q6
®
Input symbol
0
1
b
bRqj
bRq2
bRq7
ORq1
1Rq1
bLq3
ORq1
1Rq2
bLq4
bLq5
bLq6
OLq5
1Lq5
bRqa
OLq6
1Lq6
bRqa
9.9 We have three states qQ, qj, qj, where qQ is the initial state used to
remember that even number of l's have been encountered so far. qj is
used to remember that odd number of l's have been encountered so far.
qr is the final state. The transition table is defined by Table A9.2.
TABLE A9.2 Transition Table for Exercise 9.9
Present state
o
b
9.10 The construction given in Example 9.7 can be modified. As the number
of occurrences of c is independent of that of a or b, after scanning the
rightmost c, the RJW head can move to the left and erase c.
9.11 Assume that the input tape has 0
11l 1O" where m --' - n is required. We
have the following steps:
(a) The leftmost 0 is replaced by b and the RJW head moves to the
right.
(b) The RIW head replaces the first 0 after 1 by 1 and moves to the
left. On reaching the blank at the left end the cycle is repeated.
(c) Once the 0' s to the left of l' s are exhausted, M replaces all 0' sand
l' s by b' s. a --' - b is the number of 0' s left over in the input tape
and equal to O.
(d) Once the O's to the right of l's are exhausted, nO's have been
changed to l's and n + 1 of m O's have been changed to b. M
replaces l's (there are n + II's) by one 0 and n b's. The number
of O's remaining gives the values of a --' - b. The transition table is
defined by Table A9.3.