Context-Sensitive Grammar is defined as a 4 tuple G = (V, Σ, R, S) where:

V is a finite set of elements known as variables.

Σ is a finite set of elements known as terminals

V ∩ Σ = Null (empty set)

S is an element of V and is known as the start variable.

R is a fine set of elements known as Production Rules. Each rule is like aAb -> ayb where A is in V, a and b is in (V union Σ) and y is in (V union Σ)+.

The following is an example of this type of grammar that I found a lot in the literature.

  1. $s \to abc|aAbc$
  2. $Ab \to bA$
  3. $Ac \to Bbcc$
  4. $bB \to Bb$
  5. $aB \to aa | aaA$

my question is: how this example could be of this type if there is no context for production 4 and 2?


1 Answer 1


You are right: the grammar in your example is strictly speaking not context-sensitive. It is a monotonic (or non-contracting) grammar. In those grammars the main restriction is that the lefthand side of a production rule cannot be longer than the righthand side.

A grammar is monotonic if its productions are of the form $\alpha \to \beta$ with $1\le |\alpha| \le |\beta|$. (Some sources require $\alpha$ to have at least one terminal symbol.)

A grammar is context-sensitive if its productions are of the form $\alpha A \beta \to \alpha \gamma \beta$, with $A$ a nonterminal symbol and $|\gamma| \ge 1$. (This is basically a context-free production $A \to \gamma$ which is only allowed in context $\alpha A \beta$. )

The two grammar types are equivalent. First, every context-sensitive grammar is also monotonic. Conversely, it seems to be hard to construct a context-sensitive grammar from scratch, but there is a simple algorithm to convert from monotonic to context-sensitive. Therefore most people are using the terminology alternately.

For an example of this conversion, see the detailed answer by John L which constructs a monotonous grammar for $\{x\#x^R\#x\mid x\in\{a,b\}^∗\}$ and from there a context-sensitive grammar for the same language using the standard technique.

Note the length restriction is essential. If we are allowed to shorthen the string, then we obtain the type-0 (or unrestricted) grammar.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.