# Confusion related to context sensitive grammar

I have this confusion related to context sensitive grammar. I was referring to this article http://en.wikipedia.org/wiki/Context-sensitive_grammar. 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?

-
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

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$.
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