Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have this confusion related to context sensitive grammar. I was referring to this article And it has given an example of production rules for a context sensitive grammer like

$$\begin{align} S&\to aSBC\\ S&\to aBC\\ CB&\to HB\\ HB&\to HC\\ HC&\to BC\\ aB&\to ab\\ bB&\to bb\\ bC&\to bc\\ cC&\to cc \end{align}$$

I am a bit confused about how the rule $S \to aSBC$ fits the definition of a context sensitive grammar. I mean there is no context here.

Normally for context sensitive grammar we have rules like

$$\alpha A\beta \to \alpha \omega\beta\quad\text{ where $\omega$ is not null}$$

But in this example $S\to aSBC$ what are $\alpha$ and $\beta$. Are they null? If they are null and I have this rule $AB\to CD$, then it is also valid, since I am taking the $\alpha$ and $\beta$ as null well so it is a perfectly valid rule for context sensitive. In fact I can have any rule if I go this way, there is no restriction? It just doesn't need to be contracting and then everything is a context sensitive grammar?

share|cite|improve this question
For the grammar to be context-sensitive you need only that one of its rules are context-sensitive. Although S->aSBC isn't, there are plenty others in your example that are (for example, cC->cc). – Fixee Sep 12 '12 at 13:58
@Fixee but according to the definition it says that all the rules need to be context sensitive. It's only in the case of type 0 grammar, one is enough isn't it? – user34790 Sep 12 '12 at 14:29
The definition given in Wikipedia allows the context to be empty: "α,β ∈ (N U Σ)*" – Gareth Rees Sep 12 '12 at 16:39
up vote 2 down vote accepted

The rule $S \to aSBC$ does fit the pattern $\alpha A\beta \to \alpha \omega\beta$ with non-null $\omega$: $\alpha=\lambda=\beta$, $S=A$, and $aSBC=\omega$. Either side of the context is permitted to be empty. The production $AB\to CD$ cannot be made to fit this pattern, however. In order to match $AB$ with $\alpha A\beta$, you must either match $A$ of $AB\to CD$ with $A$ of the pattern and $B$ with $\beta$, in which case the righthand side should end in $B$, or match $B$ of $AB\to CD$ with $A$ of the pattern and $A$ with $\alpha$, in which case the righthand side should begin with $A$.

What is true is that the effect of $AB\to CD$ can be achieved using only productions that do fit the pattern. Add a new non-terminal symbol $X$ and the productions $AB\to AX$, $AX\to CX$, and $CX\to CD$. The first has contexts $\alpha=A,\beta=\lambda$; the second, $\alpha=\lambda,\beta=X$; and the third, $\alpha=C,\beta=\lambda$.

share|cite|improve this answer
Indeed context sensitive languages are sometimes defined using monotonous (or noncontracting) grammars. They allow any rules of the form $\alpha\to \beta$ with $|\alpha| \le |\beta|$. As Brian points out these are equivalent to proper context-sensitive grammars. Sometimes they are more easy to "program", as we can introduce rules like $aB\to Ba$ to indicate that $B$ moves to the left in a string of $a$'s. – Hendrik Jan Jan 1 '13 at 20:11

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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