7. One stack will keep the contents of the tape to the right of some reference
point, the other stack the tape contents to the left. Left and right moves are
then done simply by popping and pushing the stack.
Section 10.4
3. An algorithm, in outline, is as follows.
(i) Start with a copy of the preceding string.
(ii) Find the rightmost 0. Change it to a 1. Then change all the 1’s to the
right of this to 0’s.
(iii) If there are no 0’s, change all 1’s to 0’s and add a 1 on the left.
(iv) Repeat from step (i).
8. Let S 1 = {s 1 , s 2 ,…} and S 2 = {t 1 , t 2 ,…}. Then their union can be enumerated
by
If some s i = t j , we listitonly once. The union of the two sets is therefore
countable. For S 1 × S 2 , use the ordering in Figure 10.17.
Section 10.5
2. First, divide the input by two and move the result to one part of the tape. This
free space, initially occupied by the input, can then be used to store
successive divisors.
4. (e) Use a three-track machine as shown below. On the third track, we
keep the current trial value for |w|. On the second track, we place
dividers every |w| cells. We then compare the cell contents between the
markers.
6. Use Exercise 15, Section 6.2, to find a grammar in two-standard form. Then