7.4Standard decidable and undecidable problems
The idea
Memorise the decidable vs undecidable list: it separates finite-state and context-free questions from deep questions about CFGs and TMs.
Think of it like this: A map of what you can and cannot check mechanically.
Why it exists
This list answers a large share of decidability questions directly.
How it works
- Decidable: DFA/NFA/regex emptiness, equivalence, membership; CFG membership, emptiness, finiteness; TM halting within k steps.
- Undecidable: CFG ambiguity, equivalence, universality, intersection emptiness, PCP.
- Undecidable: TM halting, emptiness, equivalence, regularity.
- Trick: DPDA equivalence is decidable.
Worked example: Two CFGs equal?
Undecidable. Two DFAs equal? Decidable (minimise both and compare, or test the symmetric difference for emptiness).
Now play with it
- →Look at the table and quiz yourself row by row.
| Problem | Decidable? |
|---|---|
| DFA / NFA / regex: emptiness, equivalence, membership | Decidable |
| CFG: membership (CYK), emptiness, finiteness | Decidable |
| TM halts within k steps | Decidable |
| CFG ambiguous? | Undecidable |
| CFG: L(G) = Σ* ? ; L(G₁) = L(G₂) ? | Undecidable |
| CFG: L(G₁) ∩ L(G₂) empty? | Undecidable |
| Post correspondence problem | Undecidable |
| TM: halting, emptiness, equivalence, regularity | Undecidable |
| Is L(M) recursive? | Undecidable |
Memorise the split: finite-state and context-free membership/emptiness are decidable; everything deep about CFGs (equality, universality, ambiguity) and TMs is not.
Check yourself
Which problem is decidable?
Exam notes (the dense version)
Decidable: emptiness/equivalence of DFAs, membership in a CFG, emptiness of a CFG, finiteness of a CFG, whether M halts within k steps. Undecidable: halting, emptiness/equality/regularity of a TM, CFG ambiguity, CFG equivalence and universality, whether L(G₁) ∩ L(G₂) is empty, Post's correspondence problem.
Previous year questions: Decidability & Undecidability (7)
PYQs are grouped by topic, so this is the full set for Decidability & Undecidability; try the ones that match this subtopic. Open all 7 on the topic page.