This page summarizes closure properties for context-free languages. Our earlier handout on regular languages covered the basic idea of closure and how to use closure properties to prove non-regularity. Everything is very similar for context-free languages, except that they aren't closed under as wide a range of operations.

Context-free languages are closed under several common operations.

- Union
- Suppose we have grammars for two languages, with start symbols S and T. Rename variables as needed to ensure that the two grammars don't share any variables. Then construct a grammar for the union of the languages, with start symbol Z, by taking all the rules from both grammars and adding a new rule Z -> S | T.
- Concatenation
- Suppose we have grammars for two languages, with start symbols S and T. Rename variables as needed to ensure that the two grammars don't share any variables. Then construct a grammar for the union of the languages, with start symbol Z, by taking all the rules from both grammars and adding a new rule Z -> ST.
- Star
- Suppose that we have a grammar for the language L, with start symbol S. The grammar for L
^{*}, with start symbol T, contains all the rules from the original grammar plus the rule T -> TS | ε.- String reversal
- Reverse the character string on the righthand side of every rule in the grammar.
- Homomorphism
- Suppose that we have a grammar G for language L and a homomorphism h. To construct a grammar for h(L), modify the righthand side of every rule in G to replace each terminal symbol t with its image h(t) under the homomorphism.
- Intersection with a regular language
- The intersection of a context-free language and a regular language is always context-free. To show this, assume we have a PDA M accepting the context-free language and a DFA N accepting the regular language. Use the product construction to create a PDA which simulates both machines in parallel. This works because only M needs to manipulate the stack; N never touches the stack.

Context-free languages are ** not** closed under set intersection
or set complement.

- Intersection
- Consider the languages L
_{1}and L_{2}defined by L_{1}= {a^{n}b^{n}c^{j}: n,j ≥ 0} and L_{2}= {a^{j}b^{n}c^{n}: n,j ≥ 0}. They are both context-free. However, their intersection is the language L = {a^{n}b^{n}c^{n}: n ≥ 0}. We used the pumping lemma to show that L is not context-free.- Set complement
- There are two approaches to showing this. First, you can use deMorgan's laws to show that closure under set complement plus closure under union would imply closure under intersection.
Alternatively, there are concrete examples of context-free languages whose closure isn't context free. For example, consider L

_{3}= {a^{i}b^{j}c^{k}: i != j or j != k}. It's fairly easy to build a context-free grammar for L_{3}. Suppose its complement L'_{3}were context-free. Then L'_{3}∩ a^{*}b^{*}c^{*}would be context-free. But this language is just {a^{n}b^{n}c^{n}: n ≥ 0}, which we know not to be regular.Another example is L = {w#w : w in {a,b}

^{*}}. We can show that L is not context-free using the pumping lemma. However, it's not too hard to build a context-free grammar for the complement of L.

Like regular languages, context-free languages are not closed under
the subset/superset relationship. For example,
a^{*}b^{*}c^{*}
is context-free (in fact regular), but contains the non-context-free subset
a^{n}b^{n}c^{n}.
And a^{n}b^{n}c^{n}
contains the context-free subset {abc, aabbcc, aaabbbccc}.

Let L={w in {a,b,c}^{*} with equal numbers of a's, b's, and c's}.
L is not context-free.

To show this, suppose L were context free. Consider L' = L ∩
a^{*}b^{*}c^{*}.
Because context-free languages are closed under intersection with
regular languages, L' must be regular.
But L' is just a^{n}b^{n}c^{n}, which
we know not to be regular. So we must have been wrong in our
assumption that L was regular.