First, I wasn't sure where to ask this, so I apologize if this is the wrong thread.(adsbygoogle = window.adsbygoogle || []).push({});

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.

**Physics Forums - The Fusion of Science and Community**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Context-free Grammar and Chomsky Normal Form

Can you offer guidance or do you also need help?

Draft saved
Draft deleted

Loading...

Similar Threads - Context free Grammar | Date |
---|---|

Calculating the Force of Friction between surfaces but in a not so trivial context | May 20, 2017 |

How I can determine the free surface level? | Mar 26, 2017 |

Simple bending moment calculation | Mar 10, 2017 |

Ansys Maxwell: Set solution context error | Aug 23, 2015 |

Operator splitting? What is it in the context of transport modeling? | Apr 3, 2011 |

**Physics Forums - The Fusion of Science and Community**