HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Why are four context sensitive grammar (CSG) rules needed to represent AB -> CD?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
whyneededrepresentarefourgrammarcsgcontextrulessensitive

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#111006, answer score: 5

Revisions (0)

No revisions yet.