1. (12 points) Over the alphabet 0,,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, - R). (b) Draw the state diagram of a Tring machine that recognizes ND and is a decider. Briefly ustify 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 o:O.RI10:0.R O:O.LI1:1.L q6 q3 q4 q2 q.0 State diagram for enumerator enumerating 10, 1)*. 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 Bonus not for credit: Could you generalize these constructions to work with the analogous For reference, we provide a state diagram of an enumerator that enumerates 10,1)*, printing OR explaining why it cannot exist. language over a larger alphabet 10,1,2...,9)? strings in string order 1. (12 points) Over the alphabet 0,,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, - R). (b) Draw the state diagram of a Tring machine that recognizes ND and is a decider. Briefly ustify 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 o:O.RI10:0.R O:O.LI1:1.L q6 q3 q4 q2 q.0 State diagram for enumerator enumerating 10, 1)*. 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 Bonus not for credit: Could you generalize these constructions to work with the analogous For reference, we provide a state diagram of an enumerator that enumerates 10,1)*, printing OR explaining why it cannot exist. language over a larger alphabet 10,1,2...,9)? strings in string order
