Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Grammar to Chomsky Normal Form

  1. Nov 4, 2007 #1
    I have grammar:

    S -> ASA
    S -> aB
    A -> B
    A -> S
    B -> b
    B -> epsilon (empty string)

    Can someone please help me to convert this grammar to Chomsky Normal From so i can do CKY-algorithm
     
  2. jcsd
  3. Jul 19, 2008 #2
    Hi,

    S -> ASA | aB
    A -> B | S
    B -> b | eps

    your CNF grammar should be

    S -> AS | SA | CB | a
    A-> b | AS | SA | CB | a
    B -> b
    C -> a
     
  4. Jul 14, 2010 #3
    Saw this online and decided to give another version, because I'm not sure if the answer above is correct. Unless there is a rule that allows ASA -> AS | SA that I don't know about.

    (From where you left off...)
    S -> ASA | aB
    A -> B | S
    B -> b | eps

    (Step 1: remove eps productions)
    S -> ASA | aB | a
    A -> B | S
    B -> b

    (Step 2: remove unit productions)
    S -> ASA | aB | a
    A -> b | ASA | aB | a
    B -> b

    (Step 3: remove useless productions)
    none, all have terminal variable

    (Step 4: put into Chomsky form)
    S -> DA | CB | a
    A -> b | DA | CB | a
    B -> b
    C -> a
    D -> AS
     
  5. Jul 7, 2011 #4
    Can someone help me convert this Grammar to Chomsky Normal Form?

    S--->XYx
    X--->xxy
    Y--->Xw

    Thank you.
    Urgent Reply Needed
     
  6. Jul 7, 2011 #5
  7. Jun 14, 2012 #6
    help me in this
    if we have E →E+T/E-T/T
    T→T*F/T-F/F
    F→(E)/i/ε
    how we will solve using chomsky normal form
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Grammar to Chomsky Normal Form
Loading...