= 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.<Equivalence of Linear-bounded Automata and Context-sensitive Grammars by NPTEL>[Chomsky Hierarchy, module 14, lecture 1]{ref}
For $\{a^nb^nc^n:n\ge1\}$, 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.
Back to article page
