# 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 – Andrey Lebedev Mar 16 '18 at 12:07