Context-sensitive language

Remarks

Equivalently, $L$ is context-sensitive if it is generated by a noncontracting grammar, one whose rules $\alpha \to \beta$ satisfy $\abs{\alpha} \le \abs{\beta}$, again with the exception $S \to \varepsilon$. Example: $\set{a^n b^n c^n : n \ge 1}$ is context-sensitive; the rules $S \to aSBC$, $S \to aBC$, $CB \to BC$, $aB \to ab$, $bB \to bb$, $bC \to bc$, $cC \to cc$ form a noncontracting grammar for it. Non-example: a rule $AB \to A$ is not allowed, since it shortens the string and is not of the form of clause 2. Every context-free language is context-sensitive, and every context-sensitive language is decidable.