and
where A is not a suffix of any y i . Show that the grammar obtained by
replacing these productions with
is equivalent to the original grammar.
6.2 Two Important Normal Forms
There are many kinds of normal forms we can establish for context-free
grammars. Some of these, because of their wide usefulness, have been studied
extensively. We consider two of them briefly.
Chomsky Normal Form
One kind of normal form we can look for is one in which the number of symbols
on the right of a production is strictly limited. In particular, we can ask that the
string on the right of a production consist of no more than two symbols. One
instance of this is the Chomsky normal form.
Definition 6.4
A context-free grammar is in Chomsky normal form if all productions are of the
form
A → BC
or