[Overview] [Previous] [Next]

Linear-Bounded Automata

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 - {empty string}, depending on your definition of context-sensitive grammar).

We will not prove these theorems.

Copyright 1996 by David Matuszek
Last modified Apr 9, 1996