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 rule in $P$ is context-sensitive.

In words: a single non-terminal symbol may be replaced by a nonempty string, but only in its surrounding context.

Example

A grammar for $\{a^n{b}^n{c}^n\mid n\ge 1\}$

Consider the following context-sensitive grammar:

$$\begin{array}{rl}S& \to aSBC\mid abc\\ CB& \to BC\\ cB& \to bc\\ bC& \to bc\\ cC& \to cc\end{array}$$

It generates the language $\{a^n{b}^n{c}^n\mid n\ge 1\}$, which is context-sensitive but not context-free.

Here is one derivation of $aabbcc$.

1. Start with the start symbol:

$$S$$

2. Apply $S\to aSBC$ once. This adds one $a$ on the left and one $B$ and one $C$ on the right:

$$S\Rightarrow aSBC$$

3. Apply $S\to abc$ to the remaining $S$. This produces the base word:

$$aSBC\Rightarrow aabcBC$$

1. Apply $cB\to bc$ to the substring $cB$:

$$aabcBC\Rightarrow aabbcC$$

2. Apply $cC\to cc$ to the remaining $cC$:

$$aabbcC\Rightarrow aabbcc$$