Does anyone know if this is so?
Simplification the grammar
S -> XYZ
X -> AXA | BXB | Z | E
Y -> AYB | BYA | Z | E
A -> a
B -> b
Z -> Zu | Zv | E
First step: Deleting empty productions
I find:
S -> XYZ | XY | XZ | YZ | X | Y | Z
X -> AXA | BXB | Z | AA | BB
Y -> AYB | BYA | Z | AB | BA
A -> a
B -> b
Z -> Zu | Zv | u | v
The first step is correct?
Sorry, I'm not familiar with this method and cannot presently answer your question. What I am familiar with is 1) remove empty productions, 2) remove unit productions, 3) remove useless symbols.
Note that A and B can easily be eliminated at any stage by removing references to A and replacing them with a, and likewise for B and b.
I have found useful this PDF and this powerpoint.
Well I'd have to look up some stuff on the closure operator and see how it applies here, since I haven't used it to remove unit productions. Maybe post what you got for the next equivalent grammar and I can look it over? The unit productions are
S -> X
S -> Y
S -> Z
X -> Z
Y -> Z
The pdf you sent is very good. I found the following:
S = {X,Y,Z}
X = {Z}
Y = {Z}
S -> XYZ | XY | XZ | YZ | E |AXA | BXB | AA | BB | AYB | BYA | AB | BA
X -> AXA | BXB | AA | BB | Zu | Zv | u | v
Y -> AYB | BYA | AB | BA | Zu | Zv | v
A-> a
B -> b
Z -> Zu | Zv | u | v
Is this correct ?
Glad you found my link useful.
Well you omitted Y -> u and also S -> Z derivatives. So
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
A-> a
B -> b
Z -> Zu | Zv | u | v
Thank you. I forgot the Z
Last step: Remove useless symbols
1)Variables that directly and indirectly generate terminal:
{A,B,X,Y,Z,S}
All, so I can not remove anything
2) Ensure that any symbol is only from S
{S,A,B,X,Y,Z} = {a,b,u,v} I can arrive at all, so I can not remove
Correct ?
We can remove A and B as I mentioned above.
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
I just used a text editor's search-and-replace, rather than typing it all.
I believe this is the final simplified grammar.
Hmm actually considering Chomsky normal form (CNF) it looks like we would prefer the form
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
A-> a
B -> b
Z -> Zu | Zv | u | v
over
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
because the first one is much closer to CNF. I think I gave you bad advice at the end; sorry.
There are algorithms to convert any context-free grammar (CFG) into CNF. I don't have much experience with this, but it seems pretty straightforward. It basically involves (1) Simplifying, and (2) Adding new production rules/variables as necessary. For example, S -> XYZ can be changed to
And suppose hypothetically we had S -> abcd. We could deal with it as follows:
Rewrite
with
Then we deal with as above.