[Overview] [Previous] [Next]

Normal Forms of Context-Free Grammars

Chomsky Normal Form

A grammar is in Chomsky Normal Form if all productions are of the form A

BC or A

a where A, B, and C are variables and a is a terminal. Any context-free grammar that does not contain

can be put into Chomsky Normal Form.

(Most textbook authors also allow the production S so long as S does not appear on the right hand side of any production.)

Chomsky Normal Form is particularly useful for programs that have to manipulate grammars.

Greibach Normal Form

A grammar is in Greibach Normal Form if all productions are of the form A

ax where a is a terminal and x

V*.

Grammars in Greibach Normal Form are typically ugly and much longer than the cfg from which they were derived. Greibach Normal Form is useful for proving the equivalence of cfgs and npdas. When we discuss converting a cfg to an npda, or vice versa, we will use Greibach Normal Form.