The union of two context free languages is context free. The construction of a context free grammar for the union from context free grammars for the individual languages is exactly the same as for regular languages. Similarly, reversal, concatenation and Kleene star are okay, with essentially the same constructions already saw for regular languages.
The intersection of two context free languages, or the relative
complement of one with respect to another, is generally not
context free. For example, we’ve seen that the language consisting of
strings with some number of x
’s followed by the same number
of y
’s and then any positive number of z
’s is
context free. We’ve also seen that the language consisting of strings
with any positive number of x
’s, then some number of
y
’s and then the same number of z
’s is context
free. The intersection of these two languages is the language of strings
with some positive number of x
’s followed by the same
number of y
’s and then the same number of z
’s.
That language is not context free, although we don’t yet have the tools
to prove this. We will return to this example later, once we have a
pumping lemma for context free languages.
Although the intersection of context free languages needn’t be regular it is true that the intersection of a regular language and a context free language is a context free language. It is also true that if \({ L }\) is context free and \({ M }\) is regular then \({ L ∖ M }\) is context free, although \({ M ∖ L }\) needn’t be.