Closure Properties for Context-Free Languages

Closure Property (Definition)

A class of languages is closed under an operation if applying that operation to languages from the class always produces a language that is also in the class.

CFLs Closed under Union

CFLs are closed under union. If L1 and L2 are CFLs, then L1 ∪ L2 is a CFL. Proof: Create a new start variable S_new and rules S_new → S1 | S2, where S1 and S2 are the start symbols of the grammars for L1 and L2.

CFLs Closed under Concatenation

CFLs are closed under concatenation. If L1 and L2 are CFLs, then L1L2 = {xy | x∈L1, y∈L2} is a CFL. Proof: Create a new start variable S_new and rule S_new → S1 S2.

CFLs Closed under Kleene Star

CFLs are closed under Kleene star. If L is a CFL, then L* is a CFL. Proof: Create a new start variable S_new and rules S_new → S_new S | ε, where S is the start symbol of the grammar for L.

CFLs NOT Closed under Intersection

CFLs are NOT closed under intersection. There exist CFLs L1 and L2 such that L1 ∩ L2 is not a CFL. Example: L1 = {aⁿbⁿcᵐ}, L2 = {aᵐbⁿcⁿ} are CFLs, but L1 ∩ L2 = {aⁿbⁿcⁿ} is not a CFL.

CFLs NOT Closed under Complement

CFLs are NOT closed under complement. There exist CFLs L such that the complement ~L is not a CFL. This is a key difference from regular languages, which are closed under complement.

CFLs Closed under ∩ with Regular

CFLs are closed under intersection with a regular language. If L is a CFL and R is a regular language, then L ∩ R is a CFL. This is a useful property for proofs.

Using ∩ with Regular to Prove Non-CFL

To prove a language X is not a CFL, you can intersect it with a carefully chosen regular language R. If X ∩ R is a known non-CFL (e.g., {aⁿbⁿcⁿ}), then X itself cannot be a CFL (because if X were CFL, the intersection would have to be CFL).

Example: Proving {ww} is Non-CFL

Prove L = {ww | w ∈ {a,b}*} is not a CFL.

1. Intersect L with the regular language a*b*a*b*.
2. Result: L ∩ a*b*a*b* = {aⁿbᵐaⁿbᵐ | n,m ≥ 0}.
3. Prove (via Pumping Lemma) that {aⁿbᵐaⁿbᵐ} is not a CFL.
4. Therefore, L is not a CFL.

Example: Proving Complement of {ww} is a CFL

The complement of {ww}, i.e., L' = {x ∈ {a,b}* | x ≠ ww}, is a CFL. A grammar can be constructed that generates all strings with an odd length, or where a mismatch occurs at some mirrored position. This shows a CFL whose complement is not a CFL.

Summary: CFL Closure (Yes)

CFLs ARE closed under: Union, Concatenation, Kleene Star, Intersection with a Regular Language.

Summary: CFL Closure (No)

CFLs are NOT closed under: Intersection (general), Complement.

Key Difference from Regular Languages

Unlike regular languages, CFLs are not closed under intersection or complement. This is a major difference in their algebraic properties and computational power.