3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – Andrey Lebedev Mar 16 '18 at 12:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.