Chapter recap
CFLs are closed under ∪, concatenation, star, reversal, homomorphisms and ∩ regular, but not ∩ or complement (aⁿbⁿcᵐ ∩ aᵐbⁿcⁿ = aⁿbⁿcⁿ). DCFLs are closed under complement and ∩ regular but not ∪, ∩, concatenation, star, reversal. Emptiness, finiteness and membership (CYK, O(n³)) have algorithms; equivalence, universality and ambiguity do not. CFL pumping: |vwx| ≤ p, |vx| ≥ 1, pump v and x together. Classification ladder: bounded → regular, one deterministic comparison → DCFL, guessed → CFL, two comparisons → not CFL.
Merged rule card
From 3.4.1 Closure properties of CFLs and DCFLs
- CFL closed: ∪, concat, *, reversal, h, h⁻¹, substitution, ∩R, −R. Not: ∩, complement, difference.
- DCFL closed: complement, ∩R, ∪R, −R, h⁻¹. Not: ∪, ∩, concat, *, reversal, h.
- Counterexample: aⁿbⁿcᵐ ∩ aᵐbⁿcⁿ = aⁿbⁿcⁿ. Non-CFL proof: L ∩ R non-CFL ⇒ L non-CFL.
From 3.4.2 Algorithms for CFLs: emptiness, finiteness, membership (CYK)
- Emptiness: is S generating? Finiteness: cycle in the cleaned variable graph. Membership: CYK O(n³|G|), CNF required.
- No algorithm for general CFGs: equivalence, universality, ambiguity, regularity, emptiness of intersection.
From 3.4.3 Pumping lemma for CFLs
- L CFL ⇒ ∃p ∀z ∈ L, |z| ≥ p: z = uvwxy, |vwx| ≤ p, |vx| ≥ 1, uvⁱwxⁱy ∈ L ∀i ≥ 0. p = 2ᵏ (CNF, k variables).
- Non-CFL: aⁿbⁿcⁿ, ww, aⁿbᵐcⁿdᵐ, #a=#b=#c, a^{n²}, a^{prime}, aⁱbʲcᵏ (i<j<k).
- Unary CFL ⇒ regular. Complement of ww is a CFL.
From 3.4.4 Drill: regular, DCFL, CFL or not CFL?
- Ladder: bounded → regular; one comparison, no guess → DCFL; one comparison with a guess → CFL; two comparisons / crossing / copy / squares → not CFL.
- “or” of comparisons → CFL not DCFL; “and” → not CFL.
- Always check finiteness and collapses (unions that become a*b*).
Practice questions
- MSQ
L₁ is a CFL, L₂ is a DCFL, R is regular. Which are always CFLs?
- L₁ ∪ R
- L̅₂ ∪ L₁
- L₁ ∩ L₂
- L₁*
- MCQ
Which has no algorithm for arbitrary CFGs?
- membership
- emptiness
- finiteness
- universality (L = Σ*)
- NAT
CYK cells for a string of length 10?
Write your answer before opening the key.
- MCQ
Which is the CFL pumping split?
- xyz, |xy| ≤ p
- uvwxy, |vwx| ≤ p, |vx| ≥ 1
- uvwxy, |uv| ≤ p
- xyz, |y| ≤ p
- MSQ
Which are not CFLs?
- { aⁿbⁿcⁿ }
- { a^{p} : p prime }
- { ww }
- { wwᴿ }
- MCQ
{ aⁿbⁿ } ∪ { aⁿb²ⁿ } is:
- regular
- DCFL
- CFL but not DCFL
- not CFL
- MCQ
DCFLs are closed under which?
- union
- reversal
- complement
- Kleene star
- MSQ
Which are DCFLs?
- { aⁿbᵐcⁿ }
- balanced parentheses
- { wwᴿ }
- { aⁿbⁿcᵐdᵐ }
Answer key
Reveal answers when you’re ready
- ABD — L̅₂ is a DCFL (so a CFL), union keeps CFL.
- C: Intersection of CFLs can fail.
- D — Universality of CFGs has no algorithm.
- A: CYK.
- B: Generating test.
- C: Cycle test.
- 55 — 10·11/2.
- B — Two pumps in a short window.
- A: Regular lemma.
- C: Wrong window.
- D: Wrong.
- ABC — Standard.
- D: CFL.
- C — Union of two different ratios; a DPDA cannot decide which to check.
- A: Unbounded.
- B: Needs a guess.
- D: It is a union of two CFLs.
- C — Only complement among these.
- A: No.
- B: No.
- D: No.
- ABD — Deterministic designs exist.
- C: Needs a guess.