P11 · ALL

🔊 Listen

1 · The crucial inversion · check non-membership, not membership

ALL_CFG = {⟨G⟩ : L(G) = Σ*}. Sipser proves it undecidable by reducing from A_TM. The construction has a key inversion that students often find confusing: we don't build a CFG that recognises accepting computation histories — that would require a CFG to verify a TM, which is beyond CFG power. Instead we build a CFG that recognises everything except accepting computation histories.

Why this matters

CFGs are good at existential structure: "the string has some part that is bad." They can nondeterministically pick a position and check a local property there. They are bad at universal structure: "every part of the string is good." That requires correlating multiple positions without bounded memory — the canonical pumping-lemma failure.

A valid accepting computation history is a universal structure (every adjacent pair is correct). A broken history is existential (some adjacent pair is wrong). So the CFG checks the broken side.

The construction f(⟨M, w⟩) = ⟨G_M,w⟩

G_M,w generates string x iff x exhibits at least one of these four failures:

x is not formatted as C₁ # C₂ # … # C_ℓ.
C₁ ≠ q₀w (wrong start config).
Some adjacent pair (C_i, C_i+1) violates δ.
C_ℓ does not contain q_accept.

Then L(G_M,w) = Σ* if and only if every string fails at least one check, i.e. no valid accepting history exists for M on w, i.e. M does not accept w. A decider for ALL_CFG would decide ¬A_TM. Impossible.

🔊 Listen

2 · The reverse-write trick · why CFGs can match (C_i, C_i+1)

The grammar nondeterministically guesses where a violation occurs, then checks it locally. Crucially: the grammar accepts when it finds a violation. A correctly-formed accepting history goes through the grammar without any violation being detectable — so it is not generated.

🔊 Listen

3 · Animated demo · auto-plays · loops

🔊 Listen

4 · Pitfalls students stumble on

L(G_M,w) = Σ* is the answer. The CFG does generate everything iff M doesn't accept w. Generating everything means "every string is broken." Don't flip the direction in your head.
The reverse-write trick is not optional. Without writing alternate configurations backwards, the CFG would have to match c₁ with c_n+1 at the same position — which requires synchronisation a CFG can't do. The trick converts position-matching into adjacency-matching.
The grammar accepts the violation, not the history. Newcomers say "the grammar checks the history is correct." It does the opposite: it generates the wrong histories. The valid histories are the ones the grammar can't produce, and those are exactly the witnesses to A_TM.
Don't try to make G deterministic. CFGs are inherently nondeterministic; for each candidate violation type, the grammar nondeterministically commits to "this is where the error is." Multiple derivations may exist for the same string — that's fine, it only needs one.

🔊 Listen

5 · Q&A defence notes

Q1. Why is "find ONE violation" easier than "check ALL pairs are correct"?
Existential vs universal quantification. A CFG can nondeterministically pick a position and locally verify a single property there — that's the pushdown automaton's natural mode of operation. "No problems anywhere" requires correlating all positions simultaneously, which exceeds the CFG/PDA's bounded-stack capability. This existential/universal asymmetry is the deep reason CFGs sit strictly below TMs.
Q2. Why is the trick to write C_i+1 backwards?
In the standard construction, alternate configurations are written reversed, so checking whether (C_i, C_i+1) follow by δ becomes a palindrome-like local comparison — pairing up positions that are adjacent across the # boundary. A PDA's stack handles exactly this kind of nested matching.
Q3. What's EQ_CFG?
EQ_CFG = {⟨G₁, G₂⟩ : L(G₁) = L(G₂)}. Undecidable as an immediate corollary: fix G* with L(G*) = Σ*. Then ⟨G⟩ ∈ ALL_CFG iff ⟨G, G*⟩ ∈ EQ_CFG. A decider for EQ_CFG would decide ALL_CFG.
Q4. What is the CFG G_M,w roughly like?
A union of four "violation gadget" sub-grammars: one for each failure mode (bad format, bad start, bad δ-step, bad end). Each gadget is a small CFG that derives strings exhibiting exactly that failure. Union them with G → G_format | G_start | G_step | G_end.
Q5. Does the same trick work for LBAs?
For LBAs we don't need the reverse-write trick because LBAs can do bidirectional sweeps over the whole input. That's the asymmetry between Problem 10 (E_LBA via verifying) and this problem (ALL_CFG via violating). Both rely on computation histories, but the verification mechanics differ.

🔊 Listen

6 · Where to read more

Sipser: §5.1, Theorem 5.13 (ALL_CFG is undecidable). Lecture notes: Module 3 slide 4 covers G_M,w. Companion problems: P9 (computation histories), P10 (E_LBA, the LBA sibling), P14 (Rice's theorem — does this for arbitrary non-trivial TM properties).