strings than for short ones, generating another class of machines, the linear
bounded automata (or lba).
A linear bounded automaton, like a standard Turing machine, has an
unbounded tape, but how much of the tape can be used is a function of the input.
In particular, we restrict the usable part of the tape to exactly the cells taken by
the input. 1 To enforce this, we can envision the input as bracketed by two special
symbols, the left-end marker [ and the right-end marker ]. For an input w, the
initial configuration of the Turing machine is given by the instantaneous
description q 0 [w]. The end markers cannot be rewritten, and the read-write head
cannot move to the left of [ or to the right of ]. We sometimes say that the readwrite head “bounces” off the end markers.
Definition 10.5
A linear bounded automaton is a nondeterministic Turing machine M = (Q, Σ,
Γ,δ, q 0 , ,F), as in Definition 10.2, subject to the restriction that Σ must contain
two special symbols [ and ], such that δ (q i ,[) can contain only elements of the
form (q j , [,R), and δ (q i , ]) can contain only elements of the form (q j , ],L).
Definition 10.6
A string w is accepted by a linear bounded automaton if there is a possible
sequence of moves
for some q f ∈ F, x 1 , x 2 ∈ Γ*. The language accepted by the lba is the set of all
such accepted strings.
Note that in this definition a linear bounded automaton is assumed to be
nondeterministic. This is not just a matter of convenience but essential to the
discussion of lba's.
Example 10.4