Linear-Bounded Automata

Aka. LBA. A nondeterministic Turing machine whose read/write head is restricted to the portion of the tape occupied by the input. Tape length is bounded linearly by input length.

Formal Definition

An LBA is a nondeterministic TM $M = (Q, \Sigma, \Gamma, \delta, q_0, B, F)$ with 2 additional constraints:

• The input alphabet $\Sigma$ includes 2 special symbols: left endmarker $\lfloor$ and right endmarker $\rfloor$.
• The head never moves left of $\lfloor$ or right of $\rfloor$.

If the input has length $n$, the usable tape is exactly $n$ cells. The machine accepts by entering a final state $q_f \in F$.

Relation to Chomsky Hierarchy

LBAs accept exactly the class of context-sensitive languages (Type 1).

• If $L$ is a context-sensitive language, there exists an LBA accepting $L$.
• If an LBA accepts $L \subseteq \Sigma^*$, there exists a CSG generating $L - \{\Lambda\}$.

Comparison to TM

Example

The language $L = \{a^n b^n c^n \mid n \geq 1\}$ is context-sensitive but not context-free. An LBA accepts it:

1. Scan and mark one $a$, one $b$, one $c$ in each pass.
2. Repeat until all symbols are marked.
3. Accept if marking completes cleanly; reject if counts mismatch.

The LBA needs only the original input tape. No extra space beyond the $3n$ input cells is required.