Page 1 of 2 12 LastLast
Results 1 to 15 of 18

Math Help - Simplification grammar

  1. #1
    Super Member
    Joined
    Jun 2008
    Posts
    829

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jun 2008
    Posts
    829
    Does anyone know if this is so?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Apprentice123 View Post
    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Jun 2008
    Posts
    829
    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 ?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Apprentice123 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Jun 2008
    Posts
    829
    What I tried to do is 2) remove unit productions
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Apprentice123 View Post
    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
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member
    Joined
    Jun 2008
    Posts
    829
    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 ?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Apprentice123 View Post
    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
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Super Member
    Joined
    Jun 2008
    Posts
    829
    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 ?
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Apprentice123 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Super Member
    Joined
    Jun 2008
    Posts
    829
    OK. But remove A and B it is made in what step?
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Apprentice123 View Post
    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
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Super Member
    Joined
    Jun 2008
    Posts
    829
    Yes. Thank you

    I have not studied, the more normal form Chomsky is hard?
    Follow Math Help Forum on Facebook and Google+

  15. #15
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Apprentice123 View Post
    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

    S \to XC_1

    C_1 \to YC_2

    C_2 \to Z

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

    Rewrite S \to C_aC_bC_cC_d

    with

    C_a \to a

    C_b \to b

    C_c \to c

    C_d \to d

    Then we deal with S \to C_aC_bC_cC_d as above.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. context-free grammar
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 27th 2011, 12:51 PM
  2. Context-free grammar
    Posted in the Discrete Math Forum
    Replies: 16
    Last Post: June 29th 2010, 10:41 AM
  3. Grammar problem
    Posted in the Discrete Math Forum
    Replies: 12
    Last Post: June 29th 2010, 06:42 AM
  4. Regular Grammar
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: June 20th 2010, 09:58 AM
  5. Phrase-structure grammar
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 10th 2009, 11:01 AM

Search Tags


/mathhelpforum @mathhelpforum