2
$\begingroup$

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?

  • 0
    The definition given in Wikipedia allows the context to be empty: "α,β ∈ (N U Σ)*"2012-09-12

1 Answers 1

2

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

  • 0
    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.2013-01-01