B
Chapter 6
Simplification of
Context-Free
Grammars and
Normal Forms
efore we can study context-free languages in greater depth, we must
attend to some technical matters. The definition of a context-free
grammar imposes no restriction whatsoever on the right side of a
production. However, complete freedom is not necessary and, in fact,
is a detriment in some arguments. In Theorem 5.2, we see the
convenience of certain restrictions on grammatical forms; eliminating rules of
the form A → λ and A → B make the arguments easier. In many instances, it is
desirable to place even more stringent restrictions on the grammar. Because of
this, we need to look at methods for transforming an arbitrary context-free
grammar into an equivalent one that satisfies certain restrictions on its form. In
this chapter we study several transformations and substitutions that will be
useful in subsequent discussions.
We also investigate normal forms for context-free grammars. A normal
form is one that, although restricted, is broad enough so that any grammar has an
equivalent normal-form version. We introduce two of the most useful of these,
the Chomsky normal form and the Greibach normal form. Both have many
practical and theoretical uses. An immediate application of the Chomsky normal
form to parsing is given in Section 6.3.
The somewhat tedious nature of the material in this chapter lies in the fact
that many of the arguments are manipulative and give little intuitive insight. For
our purposes, this technical aspect is relatively unimportant and can be read
casually. The various conclusions are significant; they will be used many times
in later discussions.
Chapter 6
Simplification of
Context-Free
Grammars and
Normal Forms
efore we can study context-free languages in greater depth, we must
attend to some technical matters. The definition of a context-free
grammar imposes no restriction whatsoever on the right side of a
production. However, complete freedom is not necessary and, in fact,
is a detriment in some arguments. In Theorem 5.2, we see the
convenience of certain restrictions on grammatical forms; eliminating rules of
the form A → λ and A → B make the arguments easier. In many instances, it is
desirable to place even more stringent restrictions on the grammar. Because of
this, we need to look at methods for transforming an arbitrary context-free
grammar into an equivalent one that satisfies certain restrictions on its form. In
this chapter we study several transformations and substitutions that will be
useful in subsequent discussions.
We also investigate normal forms for context-free grammars. A normal
form is one that, although restricted, is broad enough so that any grammar has an
equivalent normal-form version. We introduce two of the most useful of these,
the Chomsky normal form and the Greibach normal form. Both have many
practical and theoretical uses. An immediate application of the Chomsky normal
form to parsing is given in Section 6.3.
The somewhat tedious nature of the material in this chapter lies in the fact
that many of the arguments are manipulative and give little intuitive insight. For
our purposes, this technical aspect is relatively unimportant and can be read
casually. The various conclusions are significant; they will be used many times
in later discussions.