Skip to content
Tape‑n‑Trace
PracticeSearch 26 tools

CFL closure lab

Hopcroft 2e §7.3. What the context-free languages are closed under, each built in front of you — and what they are not: two grammars whose intersection is aⁿbⁿcⁿ, with the pumping game that proves it. For the regular languages’ version, see the closure lab.

Hopcroft 2e §7.3.2, Thm 7.24.

L₁:
L₂:
The grammar being built — start symbol S''
  1. S → a S b
  2. S → a b
  3. S' → b S'
  4. S' → b

Narration

The two grammars must share no variable, so in the second S becomes S'.

Hopcroft 2e, §7.3.2, Thm 7.24

The shortest strings the result generates

b ab bb bbb aabb bbbb bbbbb aaabbb

Productions: S'' → S ; S'' → S' ; S → a S b ; S → a b ; S' → b S' ; S' → b

Not closed under intersection — Example 7.26
L₁ = {aⁿbⁿcⁱ | n ≥ 1, i ≥ 1}
  1. S → A B
  2. A → a A b
  3. A → a b
  4. B → c B
  5. B → c
abc abcc aabbc abccc aabbcc abcccc
L₂ = {aⁱbⁿcⁿ | n ≥ 1, i ≥ 1}
  1. S → A B
  2. A → a A
  3. A → a
  4. B → b B c
  5. B → b c
abc aabc aaabc abbcc aaaabc aabbcc

Both are context-free — the grammars are right there. Their intersection is L₁ ∩ L₂ = {aⁿbⁿcⁿ | n ≥ 1}, and the CFL pumping game proves that is not context-free (Theorem 7.18). So the CFLs are not closed under intersection, and by De Morgan not under complement or difference either (Theorem 7.29) — while intersection with a regular language always works. (The book writes this example over 0, 1, 2; the letters are renamed a, b, c to match the game.)

Questions no page of this tool decides

For context-free grammars the following are undecidable — no algorithm answers them for every grammar, so this tool does not pretend to. Where a page touches one, it reports a bounded search and says so.

  • Is G ambiguous? — the ambiguity detector searches up to a length and reports "no counterexample within bounds", never "unambiguous".
  • Do G₁ and G₂ generate the same language? — only a sample comparison is offered, labelled as a sample.
  • Is L(G₁) ∩ L(G₂) empty? — the intersection is not even context-free in general.
  • Is L(G) = Σ*? Is L(G) regular? Is the complement of L(G) context-free?

The proofs reduce from Post’s correspondence problem, in chapters this course does not prescribe. What the syllabus does cover — emptiness, finiteness and membership are decidable for CFLs — is stated in §7.4, also outside the prescribed sections.