5.3Decision properties of each class
The idea
Decision problems (membership, emptiness, equivalence ...) get harder, and finally undecidable, as the class gets more powerful.
Think of it like this: The stronger the machine, the less you can predict about it.
Why it exists
Another favourite: "which of these problems is decidable?".
How it works
- Regular: everything decidable.
- CFL: membership, emptiness, finiteness decidable; equivalence and universality are not.
- CSL: membership only.
- Recursive / RE: almost nothing is decidable.
Worked example: Equivalence
Decidable for DFAs, undecidable for CFGs, undecidable for TMs.
Now play with it
- →Read down the CFL column and note where the ✗ start.
| Problem | Regular | DCFL | CFL | CSL | Recursive | RE |
|---|---|---|---|---|---|---|
| Membership (w ∈ L?) | ✓ | ✓ | ✓ | ✓ | ✓ | ✗ |
| Emptiness | ✓ | ✓ | ✓ | ✗ | ✗ | ✗ |
| Finiteness | ✓ | ✓ | ✓ | ✗ | ✗ | ✗ |
| Equivalence (L₁ = L₂?) | ✓ | ✓ | ✗ | ✗ | ✗ | ✗ |
| Universality (L = Σ*?) | ✓ | ✓ | ✗ | ✗ | ✗ | ✗ |
| Containment (L₁ ⊆ L₂?) | ✓ | ✗ | ✗ | ✗ | ✗ | ✗ |
✓ = decidable. DCFL equivalence is decidable (Sénizergues), a result sometimes quoted as a trap. For CFLs the undecidable ones are equivalence, universality, containment and ambiguity.
Check yourself
Which is undecidable for context-free grammars?
Exam notes (the dense version)
For regular languages everything is decidable. For CFLs membership, emptiness and finiteness are decidable, but equivalence and universality are not. For TMs (recursive/RE) almost every interesting question is undecidable.
Previous year questions: Language Hierarchy & Closure Tables (7)
PYQs are grouped by topic, so this is the full set for Language Hierarchy & Closure Tables; try the ones that match this subtopic. Open all 7 on the topic page.