grammar for the language, but the process is tedious. We can get a much neater
argument with Theorem 8.5.
Let
Then, because L 1 is finite, it is regular. Also, it is easy to see that
Therefore, by the closure of regular languages under complementation and the
closure of context-free languages under regular intersection, the desired result
follows.
Example 8.8
Show that the language
is not context-free.
The pumping lemma can be used for this, but again we can get a much
shorter argument using closure under regular intersection. Suppose that L were
context-free. Then
would also be context-free. But we already know that this is not so. We conclude
that L is not context-free.
Closure properties of languages play an important role in the theory of
formal languages and many more closure properties for context-free languages
can be established. Some additional results are explored in the exercises at the
end of this section.
Some Decidable Properties of Context-Free