# Thread: Simplification grammar

1. ## Simplification grammar

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?

2. Does anyone know if this is so?

3. Originally Posted by Apprentice123
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?
You will need S -> E because E is in the language.

S -> XYZ | XY | XZ | YZ | X | Y | Z | E
X -> AXA | BXB | Z | AA | BB
Y -> AYB | BYA | Z | AB | BA
A -> a
B -> b
Z -> Zu | Zv | u | v

4. Yes. Thanks.
Next step: Take the production of type A->B

I need find the closures, correct ?

Closure_S = {X,Y,Z,A,B}
Closure_X = {A,B}
Closure_Y = {A,B}
Closure_A = empty
Closure_B = empty
Closure_Z = empty

I correct ?

5. Originally Posted by Apprentice123
Yes. Thanks.
Next step: Take the production of type A->B

I need find the closures, correct ?

Closure_S = {X,Y,Z,A,B}
Closure_X = {A,B}
Closure_Y = {A,B}
Closure_A = empty
Closure_B = empty
Closure_Z = empty

I 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.

6. What I tried to do is 2) remove unit productions

7. Originally Posted by Apprentice123
What I tried to do is 2) remove unit productions
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

8. 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 ?

9. Originally Posted by Apprentice123
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

10. 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 ?

11. Originally Posted by Apprentice123
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.

12. OK. But remove A and B it is made in what step?

13. Originally Posted by Apprentice123
OK. But remove A and B it is made in what step?
I consider A and B useless or redundant symbols.

Consider a different grammar described by

S -> SM | E
M -> m

It should be pretty easy to see that this is the same as

S -> Sm | E

14. Yes. Thank you

I have not studied, the more normal form Chomsky is hard?

15. Originally Posted by Apprentice123
Yes. Thank you

I have not studied, the more normal form Chomsky is hard?
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

$\displaystyle S \to XC_1$

$\displaystyle C_1 \to YC_2$

$\displaystyle C_2 \to Z$

And suppose hypothetically we had S -> abcd. We could deal with it as follows:

Rewrite $\displaystyle S \to C_aC_bC_cC_d$

with

$\displaystyle C_a \to a$

$\displaystyle C_b \to b$

$\displaystyle C_c \to c$

$\displaystyle C_d \to d$

Then we deal with $\displaystyle S \to C_aC_bC_cC_d$ as above.

Page 1 of 2 12 Last