Properties of Context-Free Languages

closure properties of context-free languages

Think of the context-free languages (CFLs) as a club with a strict door policy. Some ways of combining members produce someone who is STILL allowed in the club; other ways let in a stranger who does not belong. Closure properties are exactly the rules of that door: which operations keep you inside the family of context-free languages, and which can throw you out. The CFLs have a more generous door than the regular languages for some operations, but a stricter one for others — and noticing the difference is one of the first big lessons of the theory.

Concretely, if L and M are context-free, then so are their UNION L ∪ M (a string in either one — just add a new start symbol S with rules S -> S_L and S -> S_M for the two grammars), their CONCATENATION LM (a string of L followed by a string of M — use S -> S_L S_M), the KLEENE STAR L* (zero or more strings from L glued together — use S -> S_L S | ε), the REVERSAL of L (every string spelled backwards — reverse the right-hand side of every grammar rule), and the image of L under a HOMOMORPHISM (a symbol-by-symbol substitution). One mixed operation also stays inside: the INTERSECTION of a CFL with a REGULAR language is still context-free. Each closure is proved by an explicit construction on the grammar or pushdown automaton.

But here is the wall that surprises beginners: the context-free languages are NOT closed under INTERSECTION (of two CFLs) and NOT closed under COMPLEMENT. The regular languages were closed under everything; the CFLs are not. This is not a gap in our cleverness — there are concrete pairs of CFLs whose intersection is provably not context-free, and concrete CFLs whose complement is not context-free. So closure is a per-family fact you must look up, not assume: knowing a language is context-free tells you which constructions are safe and which are forbidden.

Union: from a grammar G1 generating { a^n b^n : n >= 0 } and a grammar G2 generating { b^m c^m : m >= 0 }, build S -> S1 | S2 (with G1, G2 attached). The new grammar generates the union — still context-free. But the intersection of those families' cousins (a^n b^n c^m with a^m b^n c^n) is NOT context-free, so intersection is not a safe operation here.

Closed under union, concatenation, star, reversal, homomorphism, and intersection-with-regular — but NOT under intersection or complement.

Do not carry regular-language intuition over wholesale: the regular languages are closed under intersection and complement, but the CFLs are NOT. The contrast is a genuine feature of the model, not an oversight.

Also called
CFL closure propertiesclosure of the context-free languagesCFL 對運算的封閉性