Context-sensitive grammar

A context-sensitive grammar has productions of the form $\alpha A\beta \to \alpha \gamma \beta$, where $A$ is a nonterminal symbol and $\gamma$ is a nonempty word. The surrounding words $\alpha ,\beta$ specify the context in which replacement is permitted. Every such step is length-nondecreasing.

An equivalent language-class description uses arbitrary noncontracting production rules $u\to v$ with $|u|\le |v|$ and a nonterminal in $u$. If the empty word is included, the customary exception is $S\to \epsilon$ with start symbol $S$ absent from every right side. Individual noncontracting rules need not have the displayed context-preserving form, although the generated language classes agree.

For example, $aAb\to aXYb$ replaces $A$ only when its immediate context is $a$ on the left and $b$ on the right. The language $\{a^n{b}^n{c}^n:n\ge 1\}$ is context-sensitive and is not a context-free language. The associated computational model is a linear bounded automaton, whose usable tape is bounded by a constant times input length.