A Turing machine has an infinite supply of blank tape. A *linear-bounded automaton
(lba)* is a Turing machine whose tape is only kn squares long, where n is the length of
the input (initial) string and k is a constant associated with the particular
linear-bounded automaton.

Some textbooks define an lba to use only the portion of the tape that is occupied by the input; that is, k=1 in all cases. The definitions lead to equivalent classes of machines, because we can compensate for the shorter tape by having a larger tape alphabet.

**Theorem.** For every context-sensitive language L there exists an lba M such that
L=L(M), that is, M accepts exactly the strings of L.

**Theorem.** For every language L accepted by an lba there exists a context-sensitive
grammar that produces exactly L (or L - {},
depending on your definition of context-sensitive grammar).

We will not prove these theorems.

Copyright © 1996 by David Matuszek

Last modified Apr 9, 1996