Please answer parts a, b, c
1. (12 points) Over the alphabet 0, 1,2], we define the language of non-decreasing strings to be the set of strings where there are no Os after 1s, no 0s after 2s, and no 1s after 2s. In other words, ND E0,1,2 w does not have 10, 20, or 21 as a substring) (a) Draw the state diagram of a 'luring 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, 1R (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 o:O.RI10:0,R O:O.LI1:1. L q6 x:X.RIO:1.R q.0 State diagram for enumerator enumerating 0, 13. state from the diagram (unless it's the start state), (2) any missing transitions in the state diagram have value (Ireject, - (c) Is there an enumerator that prints the strings in ND in string order? Briefly justify your answer by giving a high-level /implementation level formal definition of such an enumerator OR explaining why it cannot exist 1. (12 points) Over the alphabet 0, 1,2], we define the language of non-decreasing strings to be the set of strings where there are no Os after 1s, no 0s after 2s, and no 1s after 2s. In other words, ND E0,1,2 w does not have 10, 20, or 21 as a substring) (a) Draw the state diagram of a 'luring 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, 1R (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 o:O.RI10:0,R O:O.LI1:1. L q6 x:X.RIO:1.R q.0 State diagram for enumerator enumerating 0, 13. state from the diagram (unless it's the start state), (2) any missing transitions in the state diagram have value (Ireject, - (c) Is there an enumerator that prints the strings in ND in string order? Briefly justify your answer by giving a high-level /implementation level formal definition of such an enumerator OR explaining why it cannot exist
