Linear bounded automaton

Remarks

Example: consider a machine that first scans $\triangleleft w \triangleright$ to check that $w \in a^+ b^+ c^+$. Then, in each pass, it replaces the first unmarked $a$, $b$ and $c$ by a mark symbol $x$. It rejects if one of them is missing. It accepts when, after a pass, no unmarked letter is left; this is a linear bounded automaton for $\set{a^n b^n c^n : n \ge 1}$. It only rewrites cells between the markers, so clauses 2 and 3 hold. Non-example: a Turing machine that copies its input to the right of $\triangleright$ violates clause 2. A language is accepted by a linear bounded automaton if and only if it is context-sensitive. The same class arises if the machine may use $c \cdot n$ cells on inputs of length $n$, for a fixed constant $c$. The reason is that a larger tape alphabet compresses $c$ cells into one.