Linear bounded automaton

A linear bounded automaton is a Turing machine whose usable tape on an input of length $n$ is bounded by $cn$ cells for a fixed constant $c$. A common equivalent model places end markers around the input and permits rewriting only between them. The standard language-class characterization uses a nondeterministic machine: these machines recognize exactly the nonempty-word languages generated by context-sensitive grammars, with an explicit convention needed for the empty word.^[ref]

For $\{a^n{b}^n{c}^n:n\ge 1\}$, repeatedly mark one unmarked $a$, one $b$ and one $c$, rejecting if the order is wrong or a matching symbol is absent. Accept when no symbols remain unmarked. This uses the original input cells and repeated sweeps, showing how bounded space can check three linked counts. “Linear bounded” limits space, not running time.