Closure properties of CFLs and DCFLs

1. Which derivation does the grammar-built PDA simulate?
   Stuck? Peek at 3.3.4 CFG ↔ PDA equivalence

   • CFG → PDA: push S; expand (q, ε, A) → (q, α); match (q, a, a) → (q, ε); accept on Z₀. Simulates leftmost derivations; nondeterministic.
   • PDA → CFG: variables [p X q] (net pop of X from p to q).
   • CFG = NPDA (final state) = NPDA (empty stack). One working state suffices.

   Read lesson 3.3.4

2. Are regular languages closed under intersection?
   Stuck? Peek at 2.4.1 Closure properties of regular languages

   • Closed: ∪ ∩ − complement, concat, *, ⁺, reversal, homomorphism, inverse homomorphism, quotient (by any language), prefix, suffix, substring, substitution, finite ∪/∩.
   • Not guaranteed: infinite ∪/∩, subset, superset.
   • Prove non-regular: L ∩ R non-regular (R regular) ⇒ L non-regular.

   Read lesson 2.4.1

3. Product DFA accepting set for intersection?
   Stuck? Peek at 1.1.4 Product construction and complement

   • Product: states Q₁×Q₂, δ((p,q),a) = (δ₁(p,a), δ₂(q,a)), start (s₁,s₂).
   • ∩: F₁×F₂. ∪: F₁×Q₂ ∪ Q₁×F₂. −: F₁×(Q₂−F₂). ≤ |Q₁|·|Q₂| states.
   • Complement: complete the DFA (add dead state), swap F ↔ Q−F; same state count.
   • Regular languages closed under ∪, ∩, −, complement.

   Read lesson 1.1.4

Regular languages were closed under everything. Context-free languages are not — and the failures are exactly what GATE tests. The key reason: two stacks can’t be merged into one. Learn the table with its reasons and every closure question becomes a lookup.

L₁ = { aⁿbⁿcᵐ } and L₂ = { aᵐbⁿcⁿ } are both CFLs. What is L₁ ∩ L₂?

Prediction check

L₁ ∩ L₂ = { aⁿbⁿcⁿ } — which is not a CFL (3.4.3). So CFLs are not closed under intersection.

CFLs are closed under…

Union (S → S₁ | S₂), concatenation (S → S₁S₂), Kleene star (S → S₁S | ε), reversal (reverse every body), homomorphism and substitution (replace terminals), inverse homomorphism (PDA construction), and intersection with a regular language (run a PDA and a DFA in parallel: product states, one stack).

CFLs are NOT closed under…

• Intersection: aⁿbⁿcᵐ ∩ aᵐbⁿcⁿ = aⁿbⁿcⁿ.
• Complement: if CFLs were closed under complement, then L₁ ∩ L₂ = (L̅₁ ∪ L̅₂)̅ would be a CFL — contradiction.
• Difference L₁ − L₂: Σ* − L would give complement.

But L − R (R regular) = L ∩ R̅ is a CFL.

DCFLs

Closed under: complement (swap accepting states after making the DPDA always read its whole input), intersection with regular, union with regular, difference with regular, inverse homomorphism.

Not closed under: union, intersection, concatenation, Kleene star, reversal, homomorphism.

Example: {aⁿbⁿcᵐ} and {aᵐbⁿcⁿ} are DCFLs; their intersection is not even a CFL. Their union {aⁱbʲcᵏ : i = j or j = k} is a CFL but not a DCFL.

Using closure to prove non-CFL

If L ∩ R (R regular) is not a CFL, L is not a CFL. Example: L = { w ∈ {a,b,c}* : #a = #b = #c }. L ∩ a*b*c* = aⁿbⁿcⁿ, not a CFL ⇒ L is not a CFL.

Putting it together

• CFLs keep union, concatenation, star, reversal, homomorphisms and ∩ regular — not ∩ or complement.
• DCFLs keep complement and ∩ regular — not union, ∩, concatenation, star, reversal.
• Prove non-CFL by intersecting with a regular shape.

memory hook for the table:
  CFL : "U C S R H"  — Union, Concatenation, Star, Reversal, Homomorphism   (+ ∩R, h⁻¹)
        NOT ∩, NOT complement
  DCFL: complement ✓, ∩R ✓, h⁻¹ ✓ — everything else ✗ (union, ∩, concat, star, reversal, h)

Next: which questions about CFLs have algorithms — and the efficient membership test (CYK) that every parser descends from.

1. MSQ

   CFLs are closed under:

   1. union
   2. intersection
   3. Kleene star
   4. intersection with a regular language
2. MSQ

   DCFLs are closed under:

   1. complement
   2. union
   3. intersection with a regular language
   4. concatenation
3. MCQ

   Why are CFLs not closed under complement?

   1. PDAs cannot be complemented
   2. Closure under ∪ and complement would give closure under ∩, which fails
   3. CFLs are infinite
   4. Grammars have no complement
4. MCQ

   { w ∈ {a,b,c}* : #a = #b = #c } is:

   1. regular
   2. DCFL
   3. CFL but not DCFL
   4. not a CFL

• closure of CFLs
• closure of DCFLs
• CFL ∩ regular construction
• non-closure under ∩ and complement

1. Are CFLs closed under intersection? Counterexample?
   Reveal answer

   No: aⁿbⁿcᵐ ∩ aᵐbⁿcⁿ = aⁿbⁿcⁿ.
2. Are DCFLs closed under complement?
   Reveal answer

   Yes.
3. Are DCFLs closed under union?
   Reveal answer

   No.
4. Is CFL ∩ regular a CFL?
   Reveal answer

   Yes.