2. Show that the class of regular languages over the alphabet 0,1) is closed under the operation Reverse(L), defined as Reverse(L)= {w | w"e L} A full proof would have three stages: setup, construction, and proof of correctness. In this exercise you will focus on the setup and construction, and then apply your construction to an example Setup Consider an arbitrary NFA N = (Q, {0, 1}, , q0,F), and call the language of this NFA L Construction Build a new NFA whose language is Reverse(L). To do so, fill in the blanks where This will be the set of states for your new machine For each possible input to the transition function, specify the output Notice that r is a state in Q, and z E {0, 1 What is the initial state of N'? Make sure you choose an element of Q'. What is the set of accepting states of N'? Choose a subset of Q S((r, z)) = Application Consider the language, L, recognized by this NFA: q1 qo q2 q3 Apply your construction to this NFA and confirm that the language recognized by the resulting NFA is Reverse(L) (Bonus (not for credit): To prove that the construction of correct, we would need to prove that L(N,) Reverse(L) for any L. Fix an arbitrary but unknown language L. Let N be a NFA recognizing L, and construct N" from N as shown above. Two claims are required (1) Assume that some string, call it w, is accepted by N. Prove that w is in Reverse(L) (2) Assume that some string, call it y, is in Reverse(L). Prove that y is accepted by N" Practice your proof techniques by carrying out this justification. ]]