Thread: Simplification grammar

S -> XYZ | XY | XZ | YZ | E | aXa | bXb | aa | bb | aYb | bYa | ab | ba | Zu | Zv | u | v
X -> aXa | bXb | aa | bb | Zu | Zv | u | v
Y -> aYb | bYa | ab | ba | Zu | Zv | u | v
Z -> Zu | Zv | u | v


Turning in Chomsky Normal Form

1) Transforming the right side of length >= 2
S -> XYZ | XY | XZ | YZ | E | AXA | BXB | AA | BB | AYB | BYA | AB | BA | ZU | ZV
X -> AXA | BXB | AA | BB | ZU | ZV
Y -> AYB | BYA | AB | BA | ZU | ZV
Z -> ZU | ZV
U -> u
V -> v
A -> a
B -> b

2) Exactly two variables on the right side
S -> XK | XY | XZ | YZ | E | AN | BF | AA | BB | AP | BM | AB | BA | ZU | ZV
X -> AN | BF | AA | BB | ZU | ZV
Y -> AP | BM | AB | BA | ZU | ZV
Z -> ZU | ZV
K -> YZ
N -> XA
F -> XB
P -> YB
M -> YA
U -> u
V -> v
A -> a
B -> b

Is this correct ?

Originally Posted by Apprentice123

S -> XYZ | XY | XZ | YZ | E | aXa | bXb | aa | bb | aYb | bYa | ab | ba | Zu | Zv | u | v
X -> aXa | bXb | aa | bb | Zu | Zv | u | v
Y -> aYb | bYa | ab | ba | Zu | Zv | u | v
Z -> Zu | Zv | u | v


Turning in Chomsky Normal Form

1) Transforming the right side of length >= 2
S -> XYZ | XY | XZ | YZ | E | AXA | BXB | AA | BB | AYB | BYA | AB | BA | ZU | ZV
X -> AXA | BXB | AA | BB | ZU | ZV
Y -> AYB | BYA | AB | BA | ZU | ZV
Z -> ZU | ZV
U -> u
V -> v
A -> a
B -> b

2) Exactly two variables on the right side
S -> XK | XY | XZ | YZ | E | AN | BF | AA | BB | AP | BM | AB | BA | ZU | ZV
X -> AN | BF | AA | BB | ZU | ZV
Y -> AP | BM | AB | BA | ZU | ZV
Z -> ZU | ZV
K -> YZ
N -> XA
F -> XB
P -> YB
M -> YA
U -> u
V -> v
A -> a
B -> b

Is this correct ?

Looks good except that you dropped a few production rules of type A -> a. Compare:

S -> XK | XY | XZ | YZ | E | AN | BF | AA | BB | AP | BM | AB | BA | ZU | ZV | u | v
X -> AN | BF | AA | BB | ZU | ZV | u | v
Y -> AP | BM | AB | BA | ZU | ZV | u | v
Z -> ZU | ZV | u | v
K -> YZ
N -> XA
F -> XB
P -> YB
M -> YA
U -> u
V -> v
A -> a
B -> b

Thank you very much