Closure Properties of Context-Free Languages

What Are Closure Properties?

Closure property: If we apply an operation to CFLs, do we get another CFL?

Simple Analogy

Think of closure like family traits:

• Closed: Adding two even numbers gives even (closed under addition)
• Not closed: Adding two odd numbers gives even (not closed!)

For CFLs: Which operations preserve “CFL-ness”?

Summary Table

Closed Under Union

Theorem: If L₁ and L₂ are CFLs, then L₁ ∪ L₂ is a CFL

Proof Using CFG

Given:

• G₁ = (V₁, Σ, R₁, S₁) generates L₁
• G₂ = (V₂, Σ, R₂, S₂) generates L₂

Construct: G = (V, Σ, R, S) generating L₁ ∪ L₂

Where:

V = V₁ ∪ V₂ ∪ {S}  (combine variables + new start)
Σ = Σ  (same terminals)
S = new start symbol
R = R₁ ∪ R₂ ∪ {S → S₁ | S₂}

Key idea: New start symbol chooses which grammar to use

Example

L₁ = {aⁿbⁿ | n ≥ 0}
Grammar: S₁ → aS₁b | ε

L₂ = {aⁿb²ⁿ | n ≥ 0}
Grammar: S₂ → aS₂bb | ε

L₁ ∪ L₂:
Grammar:

S → S₁ | S₂
S₁ → aS₁b | ε
S₂ → aS₂bb | ε

Generates: {aⁿbⁿ} ∪ {aⁿb²ⁿ} = {aⁿbⁿ, aⁿb²ⁿ | n ≥ 0} ✓

Proof Using PDA

Given: PDA M₁ for L₁, PDA M₂ for L₂

Construct: PDA M for L₁ ∪ L₂

1. Add new start state q₀
2. ε-transition from q₀ to start of M₁
3. ε-transition from q₀ to start of M₂
4. Non-deterministically choose which PDA to simulate

Accept: If either M₁ or M₂ accepts

Closed Under Concatenation

Theorem: If L₁ and L₂ are CFLs, then L₁L₂ is a CFL

Proof Using CFG

Construct: G = (V, Σ, R, S) generating L₁L₂

Where:

V = V₁ ∪ V₂ ∪ {S}
R = R₁ ∪ R₂ ∪ {S → S₁S₂}

Key idea: S derives string from L₁ followed by string from L₂

Example

L₁ = {aⁿ | n ≥ 1}
Grammar: S₁ → aS₁ | a

L₂ = {bⁿ | n ≥ 1}
Grammar: S₂ → bS₂ | b

L₁L₂:
Grammar:

S → S₁S₂
S₁ → aS₁ | a
S₂ → bS₂ | b

Generates: {aⁱbʲ | i, j ≥ 1} ✓

Proof Using PDA

Construct:

1. Simulate M₁ until it accepts
2. Then simulate M₂ starting from where M₁ left off
3. Accept if M₂ accepts

Challenge: Detecting when M₁ accepts without consuming stack

Solution: Use special marker to track transitions

Closed Under Kleene Star

Theorem: If L is a CFL, then L* is a CFL

Proof Using CFG

Construct: G’ = (V’, Σ, R’, S’)

Where:

V' = V ∪ {S'}
R' = R ∪ {S' → SS' | ε}

Key idea: S’ derives zero or more strings from L

Example

L = {ab}
Grammar: S → ab

L* = {ε, ab, abab, ababab, …}
Grammar:

S' → SS' | ε
S → ab

Derivation for “abab”:

S' ⇒ SS' ⇒ abS' ⇒ abSS' ⇒ ababS' ⇒ abab ✓

Alternative Form

S' → S'S | ε

Both work! Choose based on convenience.

Closed Under Reversal

Theorem: If L is a CFL, then L^R (reversal) is a CFL

Proof Using CFG

For each production A → α:
Replace with A → α^R

Where α^R is α reversed

Example

L = {aⁿbⁿ | n ≥ 0}
Grammar: S → aSb | ε

L^R = {bⁿaⁿ | n ≥ 0}
Grammar (reversed):

S → aSb reversed = S → bSa
S → ε (unchanged)

Final: S → bSa | ε

Generates: bⁿaⁿ ✓

Proof Using PDA

Reverse PDA transitions:

• Reading a becomes reading from end
• Stack operations remain same
• Accept conditions remain same

Result: PDA for L^R

Closed Under Homomorphism

Homomorphism: Function h: Σ* → Δ* where h(ab) = h(a)h(b)

Theorem: If L is a CFL and h is a homomorphism, then h(L) is a CFL

Definition

h defined by specifying h(a) for each symbol a ∈ Σ

Examples:

h(a) = ab
h(b) = ε

Then: h(aab) = h(a)h(a)h(b) = ab·ab·ε = abab

Proof Using CFG

For each production A → a₁a₂…aₙ:
Replace with A → h(a₁)h(a₂)…h(aₙ)

Example

L = {aⁿbⁿ | n ≥ 0}
Grammar: S → aSb | ε

Homomorphism: h(a) = ab, h(b) = ba

h(L):
Grammar:

S → h(a)Sh(b) | ε
  = abSba | ε

Generates: (ab)ⁿ(ba)ⁿ ✓

Another Example

L = {w | w has equal a’s and b’s}
h(a) = a, h(b) = ε

h(L) = {aⁿ | n ≥ 0} (all a’s)

Closed Under Inverse Homomorphism

Theorem: If L is a CFL and h is a homomorphism, then h⁻¹(L) is a CFL

Definition

h⁻¹(L) = {w | h(w) ∈ L}

“All strings whose image under h is in L”

Example

L = {aⁿbⁿ | n ≥ 0}
h(a) = a, h(b) = ab

h⁻¹(L) = {w | h(w) ∈ L}

Check: h(b) = ab, h(bb) = abab = a²b²

So: bⁿ ∈ h⁻¹(L) ✓

Proof Using PDA

Construct PDA M’ for h⁻¹(L):

1. M' reads input symbol a
2. M' simulates M reading h(a)
3. M' accepts if M accepts

Key: Simulate M on transformed input

NOT Closed Under Intersection

Theorem: CFLs are NOT closed under intersection

Counterexample

L₁ = {aⁿbⁿcᵐ | n, m ≥ 1} (CFL)
Grammar:

S → AB
A → aAb | ab
B → cB | c

L₂ = {aᵐbⁿcⁿ | n, m ≥ 1} (CFL)
Grammar:

S → AB
A → aA | a
B → bBc | bc

L₁ ∩ L₂ = {aⁿbⁿcⁿ | n ≥ 1} (NOT CFL!)

Proof: Use pumping lemma to show {aⁿbⁿcⁿ} not CFL

Why This Matters

Cannot:

• Combine two context-free constraints simultaneously
• Parse languages with multiple counting requirements
• Use intersection to simplify grammars

NOT Closed Under Complement

Theorem: CFLs are NOT closed under complement

Proof (by Contradiction)

Assume: CFLs closed under complement

Then:

1. L₁ is CFL → L̄₁ is CFL
2. L₂ is CFL → L̄₂ is CFL
3. L̄₁ ∪ L̄₂ is CFL (closed under union)
4. L₁ ∩ L₂ = L̄₁ ∪ L̄₂ is CFL (De Morgan)

But: We know intersection not closed! Contradiction! ✗

Therefore: CFLs not closed under complement

Implications

Cannot:

• Automatically negate CFL definitions
• Easily describe “strings NOT in language”
• Use complement for language simplification

NOT Closed Under Difference

Theorem: CFLs are NOT closed under difference

Proof

Difference: L₁ - L₂ = L₁ ∩ L̄₂

If closed under difference:

• L₁ - L₂ is CFL
• Set L₁ = Σ* (CFL, actually regular)
• Then Σ* - L₂ = L̄₂ is CFL
• So CFLs closed under complement

But: We know they’re not! ✗

Special Case: Intersection with Regular

Theorem: If L is a CFL and R is regular, then L ∩ R is a CFL

Proof Using PDA and DFA

Construct PDA for L ∩ R:

1. States: Q × Q_DFA (product)
2. Simulate PDA and DFA in parallel
3. Accept if both accept

Formal construction:

• PDA M = (Q_P, Σ, Γ, δ_P, q₀_P, Z₀, F_P)
• DFA D = (Q_D, Σ, δ_D, q₀_D, F_D)

New PDA M’:

States: Q_P × Q_D
Start: (q₀_P, q₀_D)
Transitions:
  If δ_P(p, a, X) = (p', α) and δ_D(q, a) = q'
  Then δ'((p,q), a, X) = ((p',q'), α)
Final: F_P × F_D

Example

L = {aⁿbⁿ | n ≥ 0} (CFL)
R = {w | w starts with ‘a’} (Regular)

L ∩ R = {aⁿbⁿ | n ≥ 1} (CFL) ✓

Applications

Can filter CFLs using regular constraints:

• Parse only strings of certain form
• Add regular restrictions to context-free syntax
• Useful in compiler design

Proof Techniques Summary

For Closure ✓

CFG construction:

• Union: S → S₁ | S₂
• Concatenation: S → S₁S₂
• Star: S → SS | ε
• Reversal: Reverse productions

PDA construction:

• Combine PDAs
• Simulate operations

For Non-Closure ✗

Counterexample:

• Find specific CFLs L₁, L₂
• Show result not CFL (pumping lemma)

Proof by contradiction:

• Assume closure holds
• Derive contradiction
• Use known non-closures

Applications

Compiler Design

Can do ✓:

• Combine multiple syntax rules (union)
• Sequence grammar rules (concatenation)
• Allow repetition (star)
• Filter with regular patterns (intersection with regular)

Cannot do ✗:

• Enforce two context-free constraints (intersection)
• Negate context-free rules (complement)

Language Theory

Understanding:

• CFLs less closed than regular languages
• More powerful but less “well-behaved”
• Need multiple stacks for intersection

Practical Parsing

Use closures:

• Build complex grammars from simple ones
• Modular grammar design
• Filter with regular expressions

Important Exam Points

1. ✓ Closed: Union, concatenation, star, reversal, homomorphism, inverse homomorphism
2. ✗ NOT closed: Intersection, complement, difference
3. ✓ Special case: Intersection with regular IS closed
4. ✓ Union proof: S → S₁ | S₂
5. ✓ Concatenation proof: S → S₁S₂
6. ✓ Star proof: S → SS | ε
7. ✗ Intersection counterexample: {aⁿbⁿcᵐ} ∩ {aᵐbⁿcⁿ} = {aⁿbⁿcⁿ} not CFL
8. ✗ Complement: Proved using intersection non-closure
9. ✓ Reversal: Reverse all productions
10. ✓ Intersection with regular: Simulate PDA and DFA in parallel

Common Mistakes to Avoid

✗ Mistake 1: Thinking CFLs closed under intersection
✓ Correct: NOT closed! {aⁿbⁿcⁿ} counterexample

✗ Mistake 2: Thinking CFLs closed under complement
✓ Correct: NOT closed! Proved via intersection

✗ Mistake 3: Forgetting intersection with regular IS closed
✓ Correct: Special case - CFL ∩ Regular = CFL

✗ Mistake 4: Wrong union construction S → S₁S₂
✓ Correct: Union is S → S₁ | S₂ (choice, not sequence)

✗ Mistake 5: Wrong star construction S → S₁* | ε
✓ Correct: S → SS | ε (recursive structure)

✗ Mistake 6: Thinking difference is closed
✓ Correct: NOT closed (would imply complement closed)

Practice Questions

Q1: Are CFLs closed under union?

Answer: Yes! Use S → S₁ | S₂.

Q2: Show {aⁿbⁿcᵐ} ∩ {aᵐbⁿcⁿ} = {aⁿbⁿcⁿ}

Answer: First needs equal a’s and b’s; second needs equal b’s and c’s; intersection needs all three equal.

Q3: Why aren’t CFLs closed under complement?

Answer: Would imply closure under intersection (De Morgan), but intersection not closed.

Q4: Grammar for L₁ ∪ L₂ where L₁ = {aⁿ}, L₂ = {bⁿ}

Answer: S → S₁ | S₂, S₁ → aS₁ | a, S₂ → bS₂ | b

Q5: Is L ∩ {ab} CFL if L is CFL?

Answer: Yes! {ab} is regular, CFL ∩ Regular = CFL.

Q6: Grammar for L* where L = {ab}

Answer: S → SS | ab | ε

Q7: Is L₁ - L₂ CFL if both are CFLs?

Answer: No! Difference not closed.

Q8: Grammar for L^R where L has S → aSb | ε

Answer: Reverse: S → bSa | ε

Summary

• Closed under: Union (S → S₁ | S₂), concatenation (S → S₁S₂), star (S → SS | ε)
• Also closed: Reversal (reverse productions), homomorphism, inverse homomorphism
• NOT closed: Intersection, complement, difference
• Special: Intersection with regular IS closed
• Counterexample: {aⁿbⁿcᵐ} ∩ {aᵐbⁿcⁿ} = {aⁿbⁿcⁿ} not CFL
• Complement proof: Via intersection non-closure
• Intersection with regular: Simulate PDA and DFA in parallel
• Practical: Can combine grammars, filter with regex, but can’t enforce multiple counting constraints
• Proof methods: CFG construction for closure, counterexamples for non-closure
• Applications: Compiler design, language composition, modular grammar design
• Key insight: CFLs less closed than regular languages, more powerful but less well-behaved

Understanding closure properties is essential for language composition and compiler design!