This is turing machine. Please do Q1.

1. (10 points) Let L = {w E {0, 1}* : |w| = 3", n > 0} (a) Give a high-level description of a Turing machine that decides this language (b) Draw the state diagram of the Turing machine 2. (10 points) Prove the set of languages recognized by a Turing machine is closed under intersection by giving a high level description of a Turing machine that recognizes the intersection of their two languages 3. (10 points) Prove if a language L is recognizable, then so is L*. Again, do this with a high-level description. (Hint: first solve for L o L and think in terms of the number of steps in the Turing machines.) 4. (10 points) Define a de-numerator of a language L as a machine that prints all the strings not in L in an order of non-decreasing length. Prove a language is Turing decidable if it has a de-numerator. (Hint: consider the two disjoint cases, first when the complement of L is finite and second when it is infinite. In the first case you can show L is decidable without the de-numerator 5. (10 points) Let the language A be the pairs(D, u) where D is (an encoding of) a DFA with alphabet L(D)) ? and w ?* is a string in the language of D. Formally, A = {(D, u) : D is a DFA and w Prove this language is decidable. Created by Paint X