Context-Sensitive Grammar

languages

Definition

Context-Sensitive Grammar (Type-1)

A grammar $G=(N,T,P,S)$ is called context-sensitive (Type-1) if every production in $P$ is of the form $\alpha \to \beta$ where there exist $u,v\in (N\cup T{)}^{\ast }$, $A\in N$, and $w\in (N\cup T{)}^{+}$ such that

$$\alpha =uAv\text{and}\beta =uwv.$$

In words: a single nonterminal $A$ may be replaced by a nonempty string $w$, but only in its surrounding context $u\_\square v$.