Automata B-Exam
January 1997
There are 3 questions worth 10 points each for a total of 30 points.
- Let L = {0m1n | n > m >= 1}. Which of the following
are regular sets? Justify your answers.
- L.
- L1*.
- 0*L.
- 097L.
- Show that it is undecidable whether the intersection of
two CFLs is nonempty.
-
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.