** 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:
- 1.
- both
*L* and are recursive,
- 2.
- neither
*L* nor is r.e, or
- 3.
- at most one of
*L* and is r.e, the other is not r.e.

.

*root*

*6/10/1998*