1. (12 points) Over the alphabet 10, 1,2), we define the language of non-decreasing strings to be the set of strings where there are no Os after 1s, no Os after 2s, and no 1s after 2s. In other words, ND {w {0, 1, 2)' I w does not have 10, 20, or 21 as a substring} (a) Draw the state diagram of a Turing machine that recognizes ND and is not a decider. Briefly justify your answer by explaining the role of each state. Note: You may continue to use the following conventions when drawing state diagrams of Turing machines (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, u, R). (b) Draw the state diagram of a Turing machine that recognizes ND and is a decider. Briefly justify your answer by explaining the role of each state. Note: You may continue to use the following conventions when drawing state diagrams of Turing machines (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, , R). c) Is there an enumerator that prints the strings in ND in string order? Briefly justify your answer by giving a high- level OR implementation-level definition of such an enumerator OR explaining why it cannot exist. q6 q3 0 D:D D: D q.0 prin q2 q5 State diagram for enumerator enumerating 10,1}*. 1. (12 points) Over the alphabet 10, 1,2), we define the language of non-decreasing strings to be the set of strings where there are no Os after 1s, no Os after 2s, and no 1s after 2s. In other words, ND {w {0, 1, 2)' I w does not have 10, 20, or 21 as a substring} (a) Draw the state diagram of a Turing machine that recognizes ND and is not a decider. Briefly justify your answer by explaining the role of each state. Note: You may continue to use the following conventions when drawing state diagrams of Turing machines (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, u, R). (b) Draw the state diagram of a Turing machine that recognizes ND and is a decider. Briefly justify your answer by explaining the role of each state. Note: You may continue to use the following conventions when drawing state diagrams of Turing machines (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, , R). c) Is there an enumerator that prints the strings in ND in string order? Briefly justify your answer by giving a high- level OR implementation-level definition of such an enumerator OR explaining why it cannot exist. q6 q3 0 D:D D: D q.0 prin q2 q5 State diagram for enumerator enumerating 10,1}*
