Linear-Bounded Automata

Aka. LBA. A nondeterministic Turing machine with limited-length tape. Length bounded linearly by input length. Head cannot move beyond defined bounds. Lies between PDA and TM in computational power.

If $L$ is a context-sensitive language then there exists an LBA accepting $L$.

If there exists a LBA accepting $L \subseteq \Sigma^*$ then there exists a CSG generating $L - \{\Lambda\}$.