Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
