A_DFA, E_DFA, A_CFG are all decidable

Three apparently-similar yes/no questions, all polynomial-time decidable. The TM versions of these same questions — A_TM, E_TM, equivalence — are undecidable. Understanding what changes is the entire point of the comparison.

The line between the two columns is sharper than students expect. EQ_CFG — equivalence of context-free grammars — falls on the undecidable side, even though A_CFG and E_CFG are decidable. That single fact is the warning shot: small changes in the question can flip decidability. EQ_CFG is undecidable because comparing two CFGs requires checking every string in Σ*, and that quantifier-over-Σ* pushes you out of "bounded search" land.

Take grammar G in CNF: S → AB | BC, A → BA | a, B → CC | b, C → AB | a. Input w = "baaba".

CYK builds a table T where T[i, j] holds the set of variables that derive the substring of length j starting at position i.

• Row 1 (length-1 substrings): T[1,1]={B} (b→B), T[2,1]={A,C} (a→A,C), T[3,1]={A,C}, T[4,1]={B}, T[5,1]={A,C}.
• Row 2 (length-2 substrings): for w₁w₂="ba", we look for X→YZ with Y∈T[1,1], Z∈T[2,1]. S→AB? B∈T[1,1]? Yes. A∈T[2,1]? Yes. So S → BA? Not in our rules; check rules whose RHS matches (B,A): A→BA. So T[1,2]={A}. Continue across the row.
• …fill row by row until T[1,5]. Accept iff S ∈ T[1,5].

The table has O(n²) cells, each computed in O(n·|G|) time → total O(n³·|G|).

• "Simulate" the DFA, not "convert" it. A_DFA's decider just runs the DFA mentally — no construction needed. The simplicity is the point.
• E_DFA uses graph reachability, not language minimisation. You don't need to minimise B or compute L(B) explicitly. Just check whether any accept state is graph-reachable from q₀. The decider doesn't care which accept state.
• CYK requires CNF. Don't try to run CYK directly on the input grammar — convert to Chomsky Normal Form first. The conversion is mechanical (Sipser §2.1) but takes a few transformation passes.
• EQ_CFG is undecidable. A common slip: students remember "all CFG questions are decidable" and apply that to equivalence. They aren't all decidable. Equivalence flips the table.

• Q1. Why is A_DFA decidable but A_TM isn't?
  A DFA on input of length n visits exactly n + 1 states (one per position) and the simulation always halts. A TM may loop indefinitely on its input. Halting-vs-not-halting is exactly what diagonalisation shows can't be decided in general.
• Q2. Why is E_DFA O(|Q|·|Σ|) but E_TM undecidable?
  For a DFA, "empty language" is a finite graph question: starting from q₀, is any accept state reachable? Standard BFS. For a TM, "empty language" asks whether the TM ever accepts any input from Σ* — a quantifier over all strings, with no graph to walk because the configuration space is infinite.
• Q3. Where does CYK's O(n³) come from?
  Table T[i, j] has O(n²) entries (start position × length). Computing T[i, j] tries O(j) split points where to break the substring, and for each split checks the constant number of rules A → BC. So total work = O(n²) · O(n) · O(|G|) = O(n³·|G|).
• Q4. Is EQ_DFA decidable?
  Yes. Build the symmetric-difference DFA C with L(C) = L(A) △ L(B). Regular languages are closed under complement, intersection, and union, so C exists and is constructible. Then L(A) = L(B) iff L(C) = ∅, which we decide via E_DFA. Total: poly-time.
• Q5. What about EQ_NFA and EQ_REX?
  Decidable but PSPACE-complete — the construction goes through DFA conversion which can incur exponential blow-up. Decidable in principle, but no known polynomial-time algorithm.

Sipser: §4.1, Theorems 4.1–4.7 (the full decidability table). Lecture notes: Module 1 covers all three constructions slide-by-slide. Companion problems: P02 (universal TM, contrast), P14 (Rice's theorem, contrast).