A (normal) enumerator is a version of a Turing machine M that has an extraoutput tape (or a printer attached, as the textbook formulates it). Both tapes are completely blank as the machine starts. M writes a sequence of strings onto the output tape with a separation symbol (e.g., a comma) between them. This sequence is nite or innite. Repetitions of strings are allowed. The generated language is the set of all the listed strings. A lexicographic enumerator is an enumerator that writes its list in shortlex order(ordered by length rst, and ordered lexicographically for each xed length).

(a) For which type of enumerator is the generated language L decidable? Explain how to decide (by a TM) the language L generated by this type of enumerator. (b) For an arbitrary decidable language L, explain how to generate L by this type of enumerator. (c) You are given an enumerator M of the other type. Informally, dene a Turing machine M recognizing the language L generated by M.