3
$\begingroup$

I am wondering if there is a described normal form for Context-sensitive grammar, which is something similar to Kuroda normal form and Greibach normal form. That is to say, each rule in such form might be one of the following:

$A\beta\rightarrow a_1\dots a_k B_1 B_2\dots B_n a_{k+1}\dots a_m$

or

$A\rightarrow a_1\dots a_k B_1 B_2\dots B_n a_{k+1}\dots a_m$

where $A,B_i\in N$, $\beta\in(N\cup T)$, $a_i\in T$, $m\geq 0$, $n\geq 0$, $k\geq 0$, $(m+n)>0$.

The idea is that three conditions are satisfied:

  1. In the left-hand side parts of rules, non-terminals always come first.
  2. In the right-hand side parts of rules all non-terminals are grouped together.
  3. Context-sensitive rules contain no more than two symbols in the left-hand side of the rule.

As an answer I would expect either a counter-example, which proves that it is not always possible to transform any context-sensitive grammar into this form, either a link to the existent paper where such normal form is described, either a proof that such normal form exists :-)

$\endgroup$
3
$\begingroup$

A set of grammars in Kuroda form $\mathcal{K}$ is a strict subset of grammars in the described form $\mathcal{L}$:$\mathcal{K}\subset\mathcal{L}$. This follows from the fact that the first form covers first three forms of Kuroda since $k$ and $m$ can be equal to $0$. And the last one covers '$A$ $\mathcal\rightarrow$ $a$' form since $k$ and $n$ can be equal to $0$.

Let $\mathcal{G}$ - set of all Context-sensitive grammars. Since it's proven that for any Context-sensitive grammar $G\in\mathcal{G}$ there is a mapping $K:\mathcal{G}\rightarrow\mathcal{K}$ (i.e. there is an algorithm of transforming any CS-grammar into Kuroda form), we can say that mapping $L:\mathcal{G}\rightarrow\mathcal{L}$ also always exists and it is equal to $K$: $L$ = $K$.

Indeed, for any $G\in\mathcal{G}$ there should be satisfied the following condition: $L(G)\in\mathcal{L}$. If $L=K$, then $L(G)\in\mathcal{K}\subset\mathcal{L}$.

Q.E.D.

$\endgroup$

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.