<p>You can find the proof in Penttonen's original research article: </p>

<p>Martti Penttonen, One-Sided and Two-Sided Context in Formal Grammars. Information and Control 25, pp. 371-392 (1974). <a href="https://doi.org/10.1016/S0019-9958(74)91049-3" rel="nofollow noreferrer">https://doi.org/10.1016/S0019-9958(74)91049-3</a></p>

CC BY-SA 3.0
2018-03-16T12:07:16.470Z
I have read the proof. But it is not really constructive. I want to understand to convert the given set of rules in Kuroda form to the Penttonen
Andrey Lebedev
CC BY-SA 4.0
2021-08-16T01:13:26.770Z
I also have read the proof but could not follow it. 
But I see Andrey's question as how to convert 
rule $r:AZ\rightarrow WZ$ into a set $RS$ of rules in Pentonnen normal form 
such that $RS$ is equal to $r$ 
as a challenge to Pentonnen's method.
To ask a more concrete question, 
how to give a grammar for $a^ib^ic^i$ in Pentonnen normal form?
Any source or hint on this?
Charles Yu
CC BY-SA 3.0
2018-03-16T11:56:27.187Z
2018-03-16T11:56:27.187Z
Hermann Gruber
<p>Let us say we have some abstract context-sensitive grammar in the <a href="https://en.wikipedia.org/wiki/Kuroda_normal_form" rel="nofollow noreferrer">Kuroda normal form</a>, which is where all production rules are of the form:</p>

<p>$AB\rightarrow CD$ or</p>

<p>$A\rightarrow BC$ or</p>

<p>$A\rightarrow B$ or</p>

<p>$A\rightarrow a$</p>

<p>There is also the one-sided normal form or the Penttonen normal form for context-sensitive grammars (described in the same wikipedia article), which is where all rules are of the form:</p>

<p>$AB\rightarrow AD$ or</p>

<p>$A\rightarrow BC$ or</p>

<p>$A\rightarrow a$</p>

<p>Question: how to generally convert a rule of the Kuroda normal form $AB\rightarrow CD$ into bunch of rules in the Pentonnen normal form? 
In particular I am stuck with understanding how to deal with an intermediate rule of the form $AZ\rightarrow WZ$.</p>

<fl.formal-languages><grammars><space-bounded><normalization>
Converting Kuroda normal form rules to the Penttonen normal form
Andrey Lebedev
# Converting Kuroda normal form rules to the Penttonen normal form

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

Let us say we have some abstract context-sensitive grammar in the [Kuroda normal form](https://en.wikipedia.org/wiki/Kuroda_normal_form), which is where all production rules are of the form:

$AB\rightarrow CD$ or

$A\rightarrow BC$ or

$A\rightarrow B$ or

$A\rightarrow a$

There is also the one-sided normal form or the Penttonen normal form for context-sensitive grammars (described in the same wikipedia article), which is where all rules are of the form:

$AB\rightarrow AD$ or

$A\rightarrow BC$ or

$A\rightarrow a$

Question: how to generally convert a rule of the Kuroda normal form $AB\rightarrow CD$ into bunch of rules in the Pentonnen normal form?
In particular I am stuck with understanding how to deal with an intermediate rule of the form $AZ\rightarrow WZ$.

**Tags:** fl.formal-languages, grammars, space-bounded, normalization


---

## 1 answers

### Answer by username_1 on 2018-03-16. Score: 2

You can find the proof in Penttonen's original research article:

Martti Penttonen, One-Sided and Two-Sided Context in Formal Grammars. Information and Control 25, pp. 371-392 (1974). <https://doi.org/10.1016/S0019-9958(74)91049-3>

> **Comments:**
> **username_0**: I have read the proof. But it is not really constructive. I want to understand to convert the given set of rules in Kuroda form to the Penttonen  
> **username_2**: I also have read the proof but could not follow it.  But I see Andrey's question as how to convert  rule $r:AZ\rightarrow WZ$ into a set $RS$ of rules in Pentonnen normal form  such that $RS$ is equal to $r$  as a challenge to Pentonnen's method. To ask a more concrete question,  how to give a grammar for $a^ib^ic^i$ in Pentonnen normal form? Any source or hint on this?  

---

