Course contentsShow
← Computer Science
Lesson 1848 of 2,87241. Context-Free LanguagesFree lesson

Closure Properties of CFLs

Understanding which operations preserve context-freeness: union, concatenation, and Kleene star.

Closure Properties of CFLs

You'll learn which operations keep context-free languages context-free—and which don't.

Just as regular languages remain regular under certain operations (union, concatenation, star), context-free languages (CFLs) have their own closure properties. Some operations preserve context-freeness; others break it.

Operations That Preserve Context-Freeness

Union: If L₁ and L₂ are CFLs, then L₁ ∪ L₂ is also a CFL. You can build a new grammar with a new start symbol S that derives either grammar: S → S₁ | S₂, where S₁ and S₂ are the original start symbols.

Concatenation: If L₁ and L₂ are CFLs, then L₁L₂ is a CFL. Create a new start symbol: S → S₁S₂.

Kleene Star: If L is a CFL, then L* is also a CFL. Use the production: S → SS₁ | ε.

Analogy: Think of these operations as additive or sequential—they layer structures without requiring deep coordination between parts.

Operations That Do NOT Preserve Context-Freeness

Intersection: The intersection of two CFLs is not always context-free. For example, {aⁿbⁿcⁿ | n ≥ 0} can be expressed as the intersection of two CFLs, but it's not itself context-free (it requires coordinating three counters simultaneously).

Complement: CFLs are not closed under complement. If they were, combined with union (which they do have), they'd also have intersection (by De Morgan's laws)—which we know they don't.

These failures highlight a fundamental limitation: PDAs can't check relationships that require comparing multiple unbounded counts simultaneously.

Key Takeaway: Context-free languages are closed under union, concatenation, and Kleene star, but not under intersection or complement—a major difference from regular languages.