JonForbes
Oct29-11, 11:54 PM
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.
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.