relation between Turing machines and linear bounded automata. Problems like
Example 10.5 are invariably solvable by a linear bounded automaton, since an
amount of scratch space proportional to the length of the input is available. In
fact, it is quite difficult to come up with a concrete and explicitly defined
language that cannot be accepted by any linear bounded automaton. In Chapter
11 we will show that the class of linear bounded automata is less powerful than
the class of unrestricted Turing machines, but a demonstration of this requires a
lot more work.
EXERCISES
1. Give details for the solution of Example 10.5.
2. Find a solution for Example 10.5 that does not require a second track as
scratch space.
3. Consider an offline Turing machine in which the input can be read only once,
moving left to right, and not rewritten. On its work tape, it can use at most n
extra cells for work space, where n is fixed for all inputs. Show that such a
machine is equivalent to a finite automaton.
4. Find linear bounded automata for the following languages.
(a) L = {a n : n = m 2 ,m ≥ 1}.
(b) L = {a n : n is a prime number}.
(c) L = {a n : n is not a prime number}.
(d) L = {ww : w ∈{a,b} + }.
(e) L = {w n : w ∈{a,b} + ,n ≥ 2}.
(f) L = {www R : w ∈{a,b} + }.
5. Find an lba for the complement of the language in Example 10.5, assuming
that Σ = {a,b}.
6. Show that for every context-free language there exists an accepting pda, such
that the number of symbols in the stack never exceeds the length of the input
string by more than one.