LBA(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 - {}, depending on your definition of context-sensitive grammar).
We will not prove these theorems.