<p>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$.<br></p>

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

<p>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}$. </p>

<p>Q.E.D.</p>

CC BY-SA 3.0
2018-01-02T12:01:28.650Z
2018-01-02T12:17:44.437Z
2018-01-02T12:17:44.437Z
Kirill Boyarintsev
<p>I am wondering if there is a described normal form for Context-sensitive grammar, which is something similar to <a href="https://en.wikipedia.org/wiki/Kuroda_normal_form" rel="nofollow noreferrer">Kuroda normal form</a> and <a href="https://en.wikipedia.org/wiki/Greibach_normal_form" rel="nofollow noreferrer">Greibach normal form</a>. That is to say, each rule in such form might be one of the following:</p>

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

<p>or</p>

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

<p>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)&gt;0$.</p>

<p>The idea is that three conditions are satisfied:</p>

<ol>
<li>In the left-hand side parts of rules, non-terminals always come first.</li>
<li>In the right-hand side parts of rules all non-terminals are grouped together.</li>
<li>Context-sensitive rules contain no more than two symbols in the left-hand side of the rule.</li>
</ol>

<p>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 :-) </p>

<fl.formal-languages><grammars>
Looking for a particular normal form for Context-sensitive grammar
Andrey Lebedev
# Looking for a particular normal form for Context-sensitive grammar

(Asked by: username_0 on 2018-01-01)

I am wondering if there is a described normal form for Context-sensitive grammar, which is something similar to [Kuroda normal form](https://en.wikipedia.org/wiki/Kuroda_normal_form) and [Greibach normal form](https://en.wikipedia.org/wiki/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 :-)

**Tags:** fl.formal-languages, grammars

---

## 1 answers

### Answer by username_1 on 2018-01-02. Score: 3 | Accepted answer

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.


---

