Key points
- For regular languages, membership, emptiness, finiteness and equivalence are all decidable.
- For CFLs, membership, emptiness and finiteness are decidable; equivalence and ambiguity are undecidable.
- Rice's theorem: every non-trivial property of RE languages is undecidable.
- The halting problem is RE but not recursive.