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

## 1 Answer

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

• 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 Mar 16, 2018 at 12:07
• 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, 2021 at 1:13