Closure properties

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.