Next: Rice's theorem applies to
Up: Decidability analysis
Previous: The Universal Language
Any nontrivial property P of the r.e. languages is undecidable.
This means that for r.e. sets you can't decide:
- 1.
- emptiness,
- 2.
- finiteness,
- 3.
- regularity,
- 4.
- context-freedom.
root
6/10/1998