Apply the techniques in the proof of Theorem 1.45 (Sipser) to convert the NFA Nc to an equivalent DFA Dc.

3. (30 point) 0 0 9 Figure 1: The NFA N, where e repre- sent the empty string Apply the techniques in the proof of Theorem 1.45 (Sipser) to convert the NFA Nc to an equivalent DFA Dc. Your answer should provide, for the DFA Dc,a finie state diagram where all the states, the starting state, all of the accepting states and all the transitions (with the corresponding labels) are displayed/drawn clearly. Show intermediate steps. THEOREM 1.45 The class of regular languages is closed under the union operation PROOF IDEA We have regular languages Ai and A2 and want to prove that A1 U A2 is regular. The idea is to take two NFAs, N and N2 for Ai and A2, and combine them into one new NFA, N Machine N must accept its input if either Ni or N2 accepts this input new machine has a new start state that branches to the start states of the old ma- chines with arrows. In this way, the new rnachine nondeterministically guesses which of the two machines accepts N will accept it, too. the input. If one of them accepts the input, We represent this construction in the following figure. On the left, we in- dicate the start and accept states of machines N and N2 with large circles and some additional states with small circles. On the right, we show how to combine Ni and N2 into N by adding additional transition arrows. N2