NEEDS TO ANSWER A,B,C

2 You are given a DFA M = (Q,E,8,90, F) with the following properties. L(M) + 0 and all strings in L(M) have length 5. Furthermore, assume that M is minimal, i.e., no DFA with fewer states accepts L(M). Note that M has a reject state qr with the property that from every state q E FU{qr} and every symbol a E, we have s(q, a) = qr. We want to construct a DFA M'. (Q', 2, 8, 46, F') recognizing (L(M))*. One solution would be as follows. Define an NFA N from M by adding a new accepting start state qn and add e-transitions form it and from all accept states to the old start state qo (see Figure 1.50 on page 62 of the textbook). Then transform N into a DFA M'. At this point, we know that if M has k states, then M' has at most 2k+1 states. We want to show that for our special L(M), we get a much smaller DFA M'. Naturally, we use the variant of the subset construction where we only introduce states of M' for subsets of states of N that can actually be reached (not for all subsets). (a) If L(M) does not contain all strings of length 5, then one set of states that shows up in the construction of M' is {qr}. What are the other sets of states of N that actually show up in the construction of M'? (b) Give a tight upper bound on the number of states of M' as a function of k? (c) Can you find an even simpler DFA M" equivalent to M'? Show how to construct M" directly from M. Hint: A solution M" with k states gets full credit, but even k 1 is possible. Remember that this construction has only to work for our special case of L(M)