The second part of the theorem follows from Theorem 8.3 and the set
identity
If the family of context-free languages were closed under complementation, then
the right side of the above expression would be a context-free language for any
context-free L 1 and L 2 . But this contradicts what we have just shown, that the
intersection of two context-free languages is not necessarily context-free.
Consequently, the family of context-free languages is not closed under
complementation.
While the intersection of two context-free languages may produce a language
that is not context-free, the closure property holds if one of the languages is
regular.
Theorem 8.5
Let L 1 be a context-free language and L 2 be a regular language. Then L 1 L 2 is
context-free.
Proof: Let
be an npda that accepts
be a dfa that accepts L 1 . We construct a push-down
automaton
that simulates the parallel action of M 1
and M 2 : Whenever a symbol is read from the input string, simultaneously
executes the moves of M 1 and M 2 . To this end we let
and define such that
if and only if