In class, we've studied Deterministic and Nondeterministic Finite Automata, called that because they have a finite number of states. What if we allow deterministic automata to have an infinite number of states, but don't change anything else? This gives us Deterministic Infinite Automata, or DIAs. For simplicity, we'll represent these states using integers Z (including negative numbers, zero, and positive numbers). We'll assume the start state is 0. That just leaves three things to specify about a DIA: The alphabet ? A set of accepting states FcZ A transition function 8 : Zx Z Because there are an infinite number of states, we can't use a normal transition diagram or table to represent the transition function, but we can use a modified transition table that specifies the function like a piecewise function in math. We let n represent the current state. For example, for an alphabet S = {a,b), the table a b n 0 n = 2a +1, a > 0 -1 n+1 means if in a negative state, stay in that state regardless of input; if in a positive even state, increment by one on an a and go to state -1 on a b; if in a positive odd state, go to state -1 on an a and increment by one on a b." Note that the -1 entries in the table mean "go to the state -1" and not "go to state n-1 (decrement by one)". Also note that, despite its compact representation, the transition function described is total, that is, it has exactly one entry for each symbol and every possible value of n. In describing DIAs in this question, you don't need to use exactly this format for describing transition functions, but make sure that your description is mathematically precise and it's clear what you mean. (a) (3 points) Assume that the above transition table is for a DIA with accepting states F = {2a| a e Z, a>0}, that is, the positive even integers. Give a regular expression (using only the standard syntax elements: a, b, c, \, * and concatenation) that accepts the same language as the above DIA. (b) (3 points) Assume that the above transition table is for a DIA with accepting states F = {2a +1a e Z, a>0}, that is, the positive odd integers. Give a regular expression (using only the standard syntax elements: a, b, c, \, * and concatenation) that accepts the same language as the above DIA. (c) (6 points) As it happens, DFAs are a special case of DIAs. Describe a procedure for turning any DFA into a DIA that recognizes the same language. For simplicity, assume the DFA is described by a (finite) set of states S represented by consecutive nonnegative integers (0 through S1 1), and the start state so is 0. Include how to construct the three necessary features of the DIA: the alphabet, the set of accepting states, and the transition function. Make sure your transition function is total, as defined above (if it is not, your automaton is not deterministic!) On the other hand, it is not the case that every DIA can be turned into a DFA: DIAs are considerably more powerful. Consider the language over the alphabet S = {a,b), consisting of strings with the same number of as and bs (but in any order). Examples of strings in this language are e, ab, ba, abbbabaa. (d) (3 points) Explain in a short paragraph why this language is not regular, that is, why it cannot be represented by a regular expression or recognized by an NFA or DFA. You do not need to give a formal proof. (e) (4 points) Construct a DIA that accepts exactly the strings in the language over the alpha- bet = {a,b} described above. Make sure to specify the set of accepting states and a total transition function. Now consider the language over the alphabet & = {()} consisting of only strings with correctly matched parentheses. This language is defined by the following grammar: P + PP (P) As we saw in class, it is not possible to construct a DFA or NFA to recognize this language. (f) (6 points) Construct a DIA that accepts exactly the strings in the language over the alpha- bet S = {()} described above. Make sure to specify the set of accepting states and a total transition function. In class, we've studied Deterministic and Nondeterministic Finite Automata, called that because they have a finite number of states. What if we allow deterministic automata to have an infinite number of states, but don't change anything else? This gives us Deterministic Infinite Automata, or DIAs. For simplicity, we'll represent these states using integers Z (including negative numbers, zero, and positive numbers). We'll assume the start state is 0. That just leaves three things to specify about a DIA: The alphabet ? A set of accepting states FcZ A transition function 8 : Zx Z Because there are an infinite number of states, we can't use a normal transition diagram or table to represent the transition function, but we can use a modified transition table that specifies the function like a piecewise function in math. We let n represent the current state. For example, for an alphabet S = {a,b), the table a b n 0 n = 2a +1, a > 0 -1 n+1 means if in a negative state, stay in that state regardless of input; if in a positive even state, increment by one on an a and go to state -1 on a b; if in a positive odd state, go to state -1 on an a and increment by one on a b." Note that the -1 entries in the table mean "go to the state -1" and not "go to state n-1 (decrement by one)". Also note that, despite its compact representation, the transition function described is total, that is, it has exactly one entry for each symbol and every possible value of n. In describing DIAs in this question, you don't need to use exactly this format for describing transition functions, but make sure that your description is mathematically precise and it's clear what you mean. (a) (3 points) Assume that the above transition table is for a DIA with accepting states F = {2a| a e Z, a>0}, that is, the positive even integers. Give a regular expression (using only the standard syntax elements: a, b, c, \, * and concatenation) that accepts the same language as the above DIA. (b) (3 points) Assume that the above transition table is for a DIA with accepting states F = {2a +1a e Z, a>0}, that is, the positive odd integers. Give a regular expression (using only the standard syntax elements: a, b, c, \, * and concatenation) that accepts the same language as the above DIA. (c) (6 points) As it happens, DFAs are a special case of DIAs. Describe a procedure for turning any DFA into a DIA that recognizes the same language. For simplicity, assume the DFA is described by a (finite) set of states S represented by consecutive nonnegative integers (0 through S1 1), and the start state so is 0. Include how to construct the three necessary features of the DIA: the alphabet, the set of accepting states, and the transition function. Make sure your transition function is total, as defined above (if it is not, your automaton is not deterministic!) On the other hand, it is not the case that every DIA can be turned into a DFA: DIAs are considerably more powerful. Consider the language over the alphabet S = {a,b), consisting of strings with the same number of as and bs (but in any order). Examples of strings in this language are e, ab, ba, abbbabaa. (d) (3 points) Explain in a short paragraph why this language is not regular, that is, why it cannot be represented by a regular expression or recognized by an NFA or DFA. You do not need to give a formal proof. (e) (4 points) Construct a DIA that accepts exactly the strings in the language over the alpha- bet = {a,b} described above. Make sure to specify the set of accepting states and a total transition function. Now consider the language over the alphabet & = {()} consisting of only strings with correctly matched parentheses. This language is defined by the following grammar: P + PP (P) As we saw in class, it is not possible to construct a DFA or NFA to recognize this language. (f) (6 points) Construct a DIA that accepts exactly the strings in the language over the alpha- bet S = {()} described above. Make sure to specify the set of accepting states and a total transition function