Context Sensitive Grammar

Aka. CSG. A grammar $G = (V, \Sigma, S, P)$ where every production $\alpha \to \beta$ satisfies $|\beta| \geq |\alpha|$.

Equivalent form: every production has the form

where:

• $A \in V$ (single non-terminal on LHS surrounded by context)
• $X \in (V \cup \Sigma)^+$ (non-empty replacement)
• $\alpha, \beta \in (V \cup \Sigma)^*$ (arbitrary context strings)

The context $\alpha$ and $\beta$ must be identical on both sides. The non-terminal $A$ is replaced only in that specific context.

Context-Sensitive Language

Aka. CSL. Languages generated by a CSG. Accepted by linear-bounded automata.

Every context-free language is context-sensitive. Not every CSL is context-free.

Example

The language $L = \{a^n b^n c^n \mid n \ge 1\}$ is CSL but not CFL. A CSG generating $L$:

Productions:

• $S \to aSBC \mid aBC$
• $CB \to BC$
• $aB \to ab$
• $bB \to bb$
• $bC \to bc$
• $cC \to cc$

The key production $CB \to BC$ allows $B$s and $C$s to swap positions, a context-sensitive rewrite that no CFG production $A \to \alpha$ can express, because the LHS has 2 non-terminals.