= 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|\leq|v|$ and a nonterminal in $u$. If the empty word is included, the customary exception is $S\to\varepsilon$ 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^nb^nc^n:n\geq1\}$ 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.
Back to article page
