Next: Decidability analysis
Up: Theorem 3
Previous: If a language and
This theorem is very important. Let L and be
complementary languages. Then one of three cases is true:
- both L and are recursive,
- neither L nor is r.e, or
- at most one of L and is r.e, the other is not r.e.