In Wikipedia of Kuroda normal form, it says

A straightforward technique attributed to György Révész transforms a grammar in Kuroda's form to Chomsky's CSG: AB → CD is replaced by four context-sensitive rules AB → AZ, AZ → WZ, WZ → WD and WD → CD.

Why are four rules needed here? Aren't three rules: AB → AZ, AZ → CZ, CZ → CD enough?


With three steps we are not forced to complete all the steps before continuing interacting with other context around the two initial letters.

In fact, Révész himself answers this question, in his Introduction to Formal Languages at archive.org, with the following example.

Note that three rules like AB → A'B, A'B → A'D, and A'D → CD are not enough to replace the rules AB → CD. For example, if we have the rules S → AB, B → DE, AB → CD in the original grammar, then this replacement makes the derivation

S ⇒ AB ⇒ A'B ⇒ A'DE ⇒ CDE

possible, though CDE is not derivable in the original grammar. Such parasitical derivations are often quite difficult to avoid when we are trying to transform a grammar into an equivalent one.


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.