[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
Agoes toBC
or
Agoes toa
where A, B, and C are variables and a is a terminal. Any context-free grammar that does not contain empty string can be put into Chomsky Normal Form.

(Most textbook authors also allow the production Sgoes toempty string 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
Agoes toax
where a is a terminal and x is a member of 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.


Copyright 1996 by David Matuszek
Last modified Mar 18, 1996