Context-Sensitive Production Rule

languages

Definition

Context-Sensitive Production Rule

A production rule is called context-sensitive if it does not decrease the length of the string and replaces a non-terminal symbol only in its surrounding context.

Formally, a rule is context-sensitive if it has the form

$$\alpha A\beta \to \alpha \gamma \beta$$

where $A\in N$, $\alpha ,\beta \in (N\cup T{)}^{\ast }$, and $\gamma \in (N\cup T{)}^{+}$.

If the start symbol $S$ does not appear on the right-hand side of any production, then $S\to \epsilon$ is also allowed.