1. Let the set of states for a DFA be S O, 1, 2, 3, 4, 5], where the start state is 0 and the final states are 2, 4 and 5. Let the equivalence relation on S for a minimum-state DFA be generated by the following set of equivalent pairs of states: The states of the minimum-state DFA are: (2 points) or 2. Given the following regular expression over the alphabet fa, b), to transform it to a regular grammar, we first transform it to an NFA as the one shown below. 0 3 2 Instead of converting this NFA to a regular grammar directly, we convert it a DFA first and then convert the DFA to a regular grammar (why?). So we construct A-closures of the above NFA A(0)-(0, 1, 2 } (1 )3( 1, 2 } (2)3( 2 } (3)3( 3 } ()- build the following tree, (3 points) (0,-10, 1 ,2) {3} and use distinct nodes of this tree (distinct nodes of the tree are identified level by level and. within each level.from left to riaht)(1 points) By constructing production rules from this FA, we get the production set of the regular grammar on the right side of the above figure. (4.5 points) By constructing production rules from this FA, we get the production set on the right side of the above figure (3.5 points). This is the production set of the regular grammar for the regular expression a*(a* + b)b aa a*b a