1. (6 points) The state diagrams of the Turing machines for this question are on the last page of the assignment. For each question below, list all and only the correct machines from the list Mi, M2, M3, or write None if there are no such machines in this list (a) Which of the machines have -(0, 1 )? (b) Which of the machines have exactly four states? (c) Which of the machines accept the string 01? (d) Which of the machines don't change any cells on their tape for all their computations!? (e) Which of the machine(s) match the following implementation level description of a Turing machine "On input string u ig-zag across the tape to visit corresponding positions counting from the left edge and the right edge of w (e.g. from first symbol to last symbol, then second symbol, then second last symbol, etc.) 2. Cross off symbols as they are visited (to pair them off) 3. If each symbol on the left side was paired with a symbol on the right, accept otherwise, reject (f) Which of the machines recognize the set (w E 0,1* w has even length)? State diagrams of Turing machines for Questions 1 and 2 . In each case, (0,1} Conventions: (1) omit the reject state from the diagram (unless it's the start state), (2) any missing transitions in the state diagram have value (greject,D, R) qacc 1:1.R 0:0,R q0 1:1,R qo q2 qacc M2 1:1.R 0:0,R q2 0:0.L q1 g0 1. (6 points) The state diagrams of the Turing machines for this question are on the last page of the assignment. For each question below, list all and only the correct machines from the list Mi, M2, M3, or write None if there are no such machines in this list (a) Which of the machines have -(0, 1 )? (b) Which of the machines have exactly four states? (c) Which of the machines accept the string 01? (d) Which of the machines don't change any cells on their tape for all their computations!? (e) Which of the machine(s) match the following implementation level description of a Turing machine "On input string u ig-zag across the tape to visit corresponding positions counting from the left edge and the right edge of w (e.g. from first symbol to last symbol, then second symbol, then second last symbol, etc.) 2. Cross off symbols as they are visited (to pair them off) 3. If each symbol on the left side was paired with a symbol on the right, accept otherwise, reject (f) Which of the machines recognize the set (w E 0,1* w has even length)? State diagrams of Turing machines for Questions 1 and 2 . In each case, (0,1} Conventions: (1) omit the reject state from the diagram (unless it's the start state), (2) any missing transitions in the state diagram have value (greject,D, R) qacc 1:1.R 0:0,R q0 1:1,R qo q2 qacc M2 1:1.R 0:0,R q2 0:0.L q1 g0