Automata B-Exam

January 1997

There are 3 questions worth 10 points each for a total of 30 points.

1. Let L = {0^m1ⁿ | n > m >= 1}. Which of the following are regular sets? Justify your answers.
   1. L.
   2. L1^*.
   3. 0^*L.
   4. 0⁹⁷L.

2. Show that it is undecidable whether the intersection of two CFLs is nonempty.

3. Show that there does not exist an r.e. list of Turing Machines such that every machine on the list is total and every recursive set is represented by some machine on the list.

   Hint: Use diagonalization.