7. Use the observation in the above exercise to show that any context-free
language not containing λ is accepted by some linear bounded automaton.
8. To define a deterministic linear bounded automaton, we can use Definition
10.5, but require that the Turing machine be deterministic. Examine your
solutions to Exercise 4. Are the solutions all deterministic linear bounded
automata? If not, try to find solutions that are.
1 In some definitions, the usable part of the tape is a multiple of the input length, where the multiple can
depend on the language, but not on the input. Here we use only the exact length of the input string, but we
do allow multitrack machines, with the input on only one track.