Hints for Homework 14
=====================

(1) (a) It's easier to describe how you would check whether a
string is a \TM encoding.   Then figure out how to use the checker
to build the enumerator.

(b) Use dovetailing (lecture 25) i.e. run an infinite set of simulations
in parallel by starting up new ones gradually as the simulation progresses.

If you write more than 2/3 of a page on this problem, you have included
too much detail.

=====================

(2) For each language, first see if you can build a recognizer.   If you
have to search an infinite set of possibilities, the recognizer might need
to use dovetailing (see problem 1 and lecture 25).   Then figure out whether
the recognizer can be made to halt on all the inputs it should reject.

=====================

(3) (a) You're looking for a simple explanation.   What's the point of the
string of c's at the end of the input string?   

(b) Well, first, what is L(D_Mw)?   It's just L_Mw, right?   So what does it
mean for L_Mw to contain at least one string?

(c) This is an easy reduction.   Use the results you've proved in parts (a) and (b).

=====================