# Converting Kuroda normal form rules to the Penttonen normal form

Let us say we have some abstract context-sensitive grammar in the 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$.

• 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? Aug 16 at 1:13