Context Sensitive Grammar

Aka. CSG. An unrestricted grammar where every production $\alpha \to \beta$ satisfies $|\beta| \geq |\alpha|$.

Equivalent form: $\alpha A \beta \to \alpha X \beta$ where:

• $X \neq \Lambda$
• $A \in V$
• $\alpha, \beta, X \in (V \cup \Sigma)^*$

Context-Sensitive Language

Aka. CSL. Languages generated by a CSG.

A language is context-sensitive iff it can be generated by a grammar in which every production has the form:

where $α, β$ and $X$ are strings of non-terminals and/or terminals, $X ≠Λ$ and $A$ is a non-terminal.