the front.
9. We need just two tapes, one that mirrors the tape of the OM, the second that
stores the state of the OM.
SM needs only two states: an accepting and a nonaccepting state.
Section 10.3
3. (i) Start at the left of the input. Remember the symbol by putting the
machine in the appropriate state. Then replace it with X.
(ii) Move the read-write head to the right, stopping (nondeterministically)
at the center of the input.
(iii) Compare the symbol there with the remembered one. If they match,
write Y in the cell. If they don't match, reject input.
(iv) With the center of the input marked with Y, we can now proceed
deterministically, alternatively moving left and right, comparing
symbols.
For a completely deterministic solution, we first find the center of the input
(e.g., by putting markers at each end, and moving them inward until they
meet).
6. Choose a value for n. To do this, generate 1, 2,…, stopping
nondeterministically at some n. Determine if the length of the input is a
multiple of n. If it is, accept. If a n ∈ L, then there is some n for which this
works.