Page 2 of 2 FirstFirst 12
Results 16 to 18 of 18

Math Help - Simplification grammar

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

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

    Follow Math Help Forum on Facebook and Google+

  3. #18
    Super Member
    Joined
    Jun 2008
    Posts
    829
    Thank you very much
    Follow Math Help Forum on Facebook and Google+

Page 2 of 2 FirstFirst 12

Similar Math Help Forum Discussions

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

Search Tags


/mathhelpforum @mathhelpforum