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

Context-free Grammar and Chomsky Normal Form

  1. Oct 29, 2011 #1
    First, I wasn't sure where to ask this, so I apologize if this is the wrong thread.

    I am trying to understand Chomsky Normal form. The textbook I have, "Elements of the Theory of Computation" by Lewis and Papadimitriou says the following:

    "The right-hand side of a rule in a context-free grammar in Chomsky normal form must have length two." It goes on to list the three types of grammar rules which violate the constraints of the Chomsky normal form.

    1) long rules, those whose right-hand side has length three or more
    2) e-rules, of the form A -> e
    3) and short rules, of the form A -> a or A -> B.

    I am fine with all of this, but when I look at other sources on the internet, they seem to contradict what my textbook (and Professor in the class) have taught. For example, I have read elsewhere that a context-free grammar is in Chomsky normal form if all its rules are of the form:

    A -> BC (A, B, C are nonterminal symbols) No contradiction here.
    A -> a (where a is a terminal symbol) This seems to contradict 3) from above.

    Could someone please explain this. Any further detail or explanation of Chomsky Normal form would also be greatly appreciated.

    Much Thanks in advance.
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted