A CLASS OF LANGUAGES IS CLOSED UNDER AN OPERATION IF APPLYING THAT OPERATION TO MEMBERS OF THE CLASS ALWAYS YIELDS A MEMBER OF THE CLASS. ── CLOSED: THE THREE EASY CASES ──────────────────────────── Given grammars G₁ with start S₁ and G₂ with start S₂ (rename variables so they share none): UNION S → S₁ | S₂ CONCATENATION S → S₁ S₂ KLEENE STAR S → S₁ S | ε THE PROOFS ARE ONE LINE EACH, and that is not an accident: these are precisely the operations regular expressions are built from, and a grammar can express them directly. ── ALSO CLOSED ───────────────────────────────────────────── REVERSAL — reverse the right-hand side of every production. SUBSTITUTION and HOMOMORPHISM — replace each terminal by a language or a string. INVERSE HOMOMORPHISM. INTERSECTION WITH A REGULAR LANGUAGE — the most useful closure property in the topic. THE PRODUCT CONSTRUCTION for CFL ∩ REGULAR: Run the PDA and the DFA IN PARALLEL. The states of the new machine are pairs (PDA state, DFA state); the stack is THE PDA'S ONLY. δ′( (q,s), a, X ) = { ((p, δ_DFA(s,a)), γ) : (p,γ) ∈ δ_PDA(q,a,X) } Accept when both components accept. IT WORKS BECAUSE ONLY ONE STACK IS NEEDED — the DFA contributes only finite state, which folds into the state component. THAT SINGLE OBSERVATION IS ALSO THE REASON THE NEXT SECTION FAILS. ── NOT CLOSED: INTERSECTION ──────────────────────────────── THE STANDARD COUNTEREXAMPLE, worth memorising exactly: L₁ = { aⁿ bⁿ cᵐ : n, m ≥ 0 } CONTEXT FREE — match the a's with the b's, let the c's be free: S → A C, A → aAb | ε, C → cC | ε L₂ = { aⁿ bᵐ cᵐ : n, m ≥ 0 } CONTEXT FREE — let the a's be free, match b's with c's: S → A B, A → aA | ε, B → bBc | ε L₁ ∩ L₂ = { aⁿ bⁿ cⁿ } ← NOT CONTEXT FREE Each language matches ONE pair using its single stack. The intersection demands BOTH pairs matched simultaneously, which would need two stacks — and a machine with two stacks is, as the next section shows, a full Turing machine. ── NOT CLOSED: COMPLEMENT ────────────────────────────────── THIS FOLLOWS FROM THE ABOVE BY DE MORGAN, and the argument is a standard exam answer: Suppose CFLs were closed under complement. They are closed under union. Then for any CFLs L₁, L₂: L₁ ∩ L₂ = complement( complement(L₁) ∪ complement(L₂) ) would be built entirely from operations preserving context-freeness, so CFLs would be closed under intersection — CONTRADICTING the counterexample above. ∎ NOTE THE FORM OF THE ARGUMENT: it proves non-closure under complement WITHOUT exhibiting a single explicit counterexample, purely from closure under union and non-closure under intersection. ── NOT CLOSED: DIFFERENCE ────────────────────────────────── Since L₁ ∩ L₂ = L₁ − (L₁ − L₂), closure under difference would give closure under intersection. NOTE HOWEVER that L − R IS context free when R is REGULAR, because L − R = L ∩ complement(R) and regular languages ARE closed under complement. ── THE COMPARISON TABLE ──────────────────────────────────── OPERATION REGULAR CONTEXT FREE DCFL ────────────────────────────────────────────────────── union YES YES NO concatenation YES YES NO Kleene star YES YES NO intersection YES **NO** NO complement YES **NO** **YES** difference YES NO NO reversal YES YES NO ∩ with a regular language YES YES YES homomorphism YES YES NO ────────────────────────────────────────────────────── THE DCFL COLUMN IS STRIKING AND OFTEN EXAMINED: DETERMINISTIC CONTEXT-FREE LANGUAGES ARE CLOSED UNDER COMPLEMENT BUT NOT UNDER UNION — the exact reverse of the general CFL case. COMPLEMENT WORKS because a DPDA is deterministic, so swapping accepting and non-accepting states works much as for a DFA (with care over ε-moves and non-halting computations). UNION FAILS because L₁ = {aⁿbⁿcᵐ} and L₂ = {aⁿbᵐcᵐ} are both DETERMINISTIC, but their union is not — a deterministic machine reading the a's cannot know whether it will need to match them against the b's or ignore them, and it must commit before finding out.

── DECIDABLE QUESTIONS ───────────────────────────────────── Given a context-free grammar G: 1. MEMBERSHIP — is w ∈ L(G)? DECIDABLE. Convert to Chomsky normal form and run CYK in O(n³·|G|). Alternatively, since CNF derivations of a length-n string take exactly 2n − 1 steps, exhaustive search of bounded depth also works. 2. EMPTINESS — is L(G) = ∅? DECIDABLE. Compute the GENERATING variables (those deriving some terminal string) by fixed-point iteration; L(G) is empty exactly when S is not generating. 3. FINITENESS — is L(G) finite? DECIDABLE. Remove useless symbols, convert to CNF, and look for a CYCLE in the dependency graph among the remaining variables. A cycle means a variable can derive a string containing itself, hence infinitely many strings. THESE THREE ARE THE ENTIRE LIST OF USEFUL DECIDABLE PROPERTIES, which is a much shorter list than the regular case offered. ── UNDECIDABLE QUESTIONS ─────────────────────────────────── Given context-free grammars G, G₁, G₂: · IS L(G₁) = L(G₂)? UNDECIDABLE · IS L(G₁) ⊆ L(G₂)? UNDECIDABLE · IS L(G₁) ∩ L(G₂) = ∅? UNDECIDABLE · IS L(G) = Σ*? UNDECIDABLE · IS L(G) REGULAR? UNDECIDABLE · IS G AMBIGUOUS? UNDECIDABLE · IS L(G) INHERENTLY AMBIGUOUS? UNDECIDABLE · IS THE COMPLEMENT OF L(G) CONTEXT FREE? UNDECIDABLE ALL ARE PROVED BY REDUCTION FROM POST'S CORRESPONDENCE PROBLEM, which appears in the Turing machine section. The pattern of such a proof: show that if the question could be answered, PCP could be solved — and PCP is known to be unsolvable. NOTE THE PARTIAL EXCEPTION: FOR **DETERMINISTIC** CONTEXT-FREE LANGUAGES, EQUIVALENCE **IS** DECIDABLE — a deep result proved by Sénizergues in 1997, over thirty years after the question was posed. Containment for DCFLs remains undecidable. THIS IS ANOTHER REASON PROGRAMMING LANGUAGES ARE DESIGNED TO BE DETERMINISTIC: the deterministic subclass is better behaved in almost every respect. ── THE COMPARISON WITH REGULAR LANGUAGES ─────────────────── QUESTION REGULAR CONTEXT FREE ────────────────────────────────────────────── w ∈ L? decidable decidable (O(n³)) L = ∅? decidable decidable L finite? decidable decidable L₁ = L₂? DECIDABLE **UNDECIDABLE** L₁ ⊆ L₂? DECIDABLE **UNDECIDABLE** L = Σ*? DECIDABLE **UNDECIDABLE** L₁ ∩ L₂ = ∅? DECIDABLE **UNDECIDABLE** ────────────────────────────────────────────── THE DIVIDING LINE IS EXACTLY WHERE ONE MIGHT EXPECT: questions about a SINGLE string or the EXISTENCE of strings remain decidable; questions COMPARING TWO LANGUAGES become undecidable. THE UNDERLYING REASON IS THE LOSS OF A CANONICAL FORM. For regular languages the minimal DFA is unique, so equivalence reduces to isomorphism. CONTEXT-FREE GRAMMARS HAVE NO COMPUTABLE CANONICAL FORM — CNF and GNF are not unique — SO THERE IS NOTHING TO COMPARE. ── THE WHOLE SECTION IN ONE VIEW ─────────────────────────── GENERATOR: context-free grammar RECOGNISER: non-deterministic pushdown automaton NORMAL FORMS: Chomsky (binary trees, for CYK) Greibach (one terminal per step, for the PDA proof) NOTATION: BNF and EBNF BOUNDARY: the pumping lemma, aⁿbⁿcⁿ excluded CLOSURE: union, concatenation, star, ∩ with regular — but NOT intersection or complement DECIDABLE: membership, emptiness, finiteness UNDECIDABLE: equivalence, ambiguity, and everything comparative AND THE SINGLE SENTENCE THAT EXPLAINS NEARLY ALL OF IT: A PUSHDOWN AUTOMATON HAS ONE STACK, READ LAST-IN-FIRST-OUT. One stack matches one nested pair — hence aⁿbⁿ yes, aⁿbⁿcⁿ no, hence no closure under intersection, hence no closure under complement. EVERY PROPERTY IN THIS TOPIC TRACES BACK TO THAT ONE ARCHITECTURAL FACT.