====================================================================
                          Exercise 3   (due Oct 29)                              
====================================================================
 
 Let L = {<M> : M accepts the strong 01 or rejects 111 (or both)}.

(a) Show that A_TM <=m L.

(b) What can you conclude from that?

(c) Show that L is recognizable. 

(d) Is it possible that A_TM <=m L^c  (the complement of C)?