Notice that in a Turing machine it is not necessary to examine the entire
input before accepting it.
7. (a)
with F = {q 3 }.
(b)
with F = {q 2 }.
10. The solution is conceptually simple, but tedious to write out in detail. The
general scheme looks something like this:
(i) Place a marker symbol c at each end of the string.
(ii) Replace the two-symbol combination ca on the left by ac and the twosymbol combination ac on the right by ca. Repeat until the two c’s meet
in the middle of the string.
(iii) Remove one of the c’s and move the rest of the string to fill the gap.
Obviously this is a long job, but it is typical of the cumbersome ways in
which Turing machines often do simple things.
12. We cannot just search in one direction since we don't know when to stop.
We must proceed in a back-and-forth fashion, placing markers at the right
and left boundaries of the searched region and moving the markers outward.
19. If the final state set F contains more than one element, introduce a new