[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
ABC
or
Aa
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
Aax
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.

Copyright © 1996 by David Matuszek

Last modified Mar 18, 1996