enumerable, but its complement is not. Therefore, by Theorem 11.4, it is not
recursive, giving us the looked-for example.
We see from this that there are indeed well-defined languages for which one
cannot construct a membership algorithm.
EXERCISES
1. Prove that the set of all real numbers is not countable.
2. Prove that the set of all languages that are not recursively enumerable is not
countable.
3. Let L be a finite language. Show that then L + is recursively enumerable.
Suggest an enumeration procedure for L + .
4. Let L be a context-free language. Show that L + is recursively enumerable and
suggest an enumeration procedure for it.
5. Show that if a language is not recursively enumerable, its complement cannot
be recursive.
6. Show that the family of recursively enumerable languages is closed under
union.
7. Is the family of recursively enumerable languages closed under intersection?
8. Show that the family of recursive languages is closed under union and
intersection.
9. Show that the families of recursively enumerable and recursive languages are
closed under reversal.
10. Is the family of recursive languages closed under concatenation?
11. Prove that the complement of a context-free language must be recursive.
12. Let L 1 be recursive and L 2 recursively enumerable. Show that L 2 − L 1 is
necessarily recursively enumerable.
13. Suppose that L is such that there exists a Turing machine that enumerates the
elements of L in proper order. Show that this means that L is recursive.