A *linear-bounded automaton* is a Turing machine
that has only the tape that its input is printed on.
There is no additional blank tape.

**Theorem.** Linear-bounded automata are *not*
equivalent to standard Turing machines.

The languages recognizable by linear-bounded automata (lbas)
are called the *context-sensitive languages.*
We will briefly touch on context-sensitive languages
later in this course.

Copyright © 1996 by David Matuszek

Last modified Mar 27, 1996