===========================================================================
CSC 363H                  Tutorial Exercises # 3                Spring 2007
===========================================================================

1-  For any language L, show that if both L and L^c are recognizable, then
    they are decidable (where L^c is the complement of L).
    (Hint:  Think of a TM that uses the recognizer for L together with the
    recognizer for L^c.)

2-  Problems (3.15) and (3.16) on page 161. In particular is the collection
    of Decidable/Recognizable Languages closed under concatenation? What
    about star?

3-  Problem (3.18) Show that a language is decidable iff some enumerator
    enumerates the language in lexicographic order.