T
Chapter 8
Properties of
Context-Free
Languages
he family of context-free languages occupies a central position in a
hierarchy of formal languages. On the one hand, context-free
languages include important but restricted language families such as
regular and deterministic context-free languages. On the other hand,
there are broader language families of which context-free languages
are a special case. To study the relationship between language families and to
exhibit their similarities and differences, we investigate characteristic properties
of the various families. As in Chapter 4, we look at closure under a variety of
operations, algorithms for determining properties of members of the family, and
structural results such as pumping lemmas. These all provide us with a means of
understanding relations between the different families as well as for classifying
specific languages in an appropriate category.
8.1 Two Pumping Lemmas
The pumping lemma given in Theorem 4.8 is an effective tool for showing that
certain languages are not regular. Similar pumping lemmas are known for other
language families. Here we will discuss two such results, one for context-free
languages in general, the other for a restricted type of context-free language.
A Pumping Lemma for Context-Free Languages
Theorem 8.1