where S 5 is a new variable and
Then
Thus we have shown that the family of context-free languages is closed
under union, concatenation, and star-closure.
Theorem 8.4
The family of context-free languages is not closed under intersection and
complementation.
Proof: Consider the two languages
or
and
There are several ways one can show that L 1 and L 2 are context-free. For
instance, a grammar for L 1 is
Alternatively, we note that L 1 is the concatenation of two context-free languages,
so it is context-free by Theorem 8.3. But
which we have already shown not to be context-free. Thus, the family of
context-free languages is not closed under intersection.