Consider an arbitrary DFA M = (Q, {0, 1}, ?, q0, F) and call the language of this DFA L. We will define an NFA whose language is the result of taking each string in L and replacing each 0 in the string with aa and each 1 in the string with ab. For example, if L = {0, 001}, then the new language is {aa, aaaaab}. The idea for this construction is to have two copies of each state to allow us to group the bits read in as pairs. The new machine is

3. Consider an arbitrary DFA M-(Q, {0, 1),?, qo, F) and call the language of this DFA L. We will define an NFA whose language is the result of taking each string in L and replacing each 0 in the string with aa and each 1 in the string with ab. For example, if L-0, 001}, then the new language is saa, aaaaab. The idea for this construction is to have two copies of each state to allow us to group the bits read in as pairs. The new machine is where " ((r, 1), a)(r2d) ?"( ((r, 2nd),a) )-{(6((r,0)), 1st)) 6((r, 2nd),b)) (8(r, 1)), 1 ) a. Apply this construction to the DFA from question 1: Draw the resulting state diagram in JFLAP, export the image as a png or jpg file, and include it as part of your submission b. Give an example of a string of length 3 for which the computation of M" on this string gets "stuck" c. If you were to use Theorem 1.39 on page 55 in the book (the "subset construction") to write an equivalent DFA to the NFA you produced in a. , how many states would the DFA hve? Your answer should take into account unreachable states. Extension: (not to sumit) is this number optimal