HHelp!!!!!

Here's the document on the theorem in case you need it

6. (12 marks) This question tests your understanding of the equivalence between DFAs and NFAs. Consider NFA M = ({91, 92}, {0,1},8,91, {91}) for defined as: 8 01 TE 91 {91, 92} {92} 42 91,92} {91} (a) (4 marks) Draw the state diagrams for M. (b) (2 marks) Based on the construction of Theorem 1.39 in the text, start to build the DFA M' that is equiva- lent to M by identifying the number of DFA states and listing them. (c) (2 marks) Identify the DFA M' starting and acceptance states. (d) (4 marks) Draw the state diagram for the DFA M' equivalent to M based on the construction of Theorem 1.39 in the text (recall the latter proves that DFAs and NFAs are equivalent). THEOREM 1.39 Every nondeterministic finite automaton has an equivalent deterministic finite automaton. PROOF IDEA If a language is recognized by an NFA, then we must show the existence of a DFA that also recognizes it. The idea is to convert the NFA into an equivalent DFA that simulates the NFA. Recall the "reader as automaton strategy for designing finite automata. How would you simulate the NFA if you were pretending to be a DFA? What do you need to keep track of as the input string is processed in the examples of NFAS you kept track of the various branches of the computation by placing a finger on each state that could be active at given points in the input. You updated the simulation by moving, adding, and removing fingers according to the way the NFA operates. All you needed to keep track of was the set of states having fingers on them. If k is the number of states of the NFA, it has 2* subsets of states. Each subset corresponds to one of the possibilities that the DFA must remember, so the DFA simulating the NFA will have 2* states. Now we need to figure out which will be the start state and accept states of the DFA, and what will be its transition function. We can discuss this more easily after setting up some formal notation. PROOF Let N = (0...0.00. F) be the NFA recognizing some language A. We construct a DFA M = (Q.9.8.40.F"recognizing A. Before doing the full construction, let's first consider the easier case wherein N has no e arrows. Later we take the e arrows into account. 1. Q' = P(Q). Every state of M is a set of states of N. Recall that PQ) is the set of subscts of Q. 2. For Re Q' and a elet 8'(R. a) = (qera) for somer ER}. If R is a state of 1, it is also a set of states of N. When M reads a symbol a in state R, it shows where a takes each state in R. Because each state may go to a set of states, we take the union of all these sets. Another way to write this expression is 8Rc) = Udr.a). 4 3. go' = (40 M starts in the state corresponding to the collection containing just the start state of N. 4. F' = {RE QR contains an accept state of N}. The machine M accepts if one of the possible states that could be in at this point is an accept state. The notation U n r ,a) means: the union of the sets (r.a) for each possible rin R. Now we need to consider the e arrows. To do so we set up an extra bit of notation. For any state R of li we define E(R) to be the collection of states that can be reached from R by going only along e arrows, including the members of R themselves. Formally, for RC let E(R) = {gl 9 can be reached from R by traveling along 0 or more e arrows}. Then we modify the transition function of M to place additional fingers on all states that can be reached by going along e arrows after every step. Replacing 8(r, c) by E(8(r.a)) achieves this effect. Thus 5'(R.) = {0 QUE E(Src)) for some reR). Additionally we need to modify the start state of M to move the fingers ini- tially to all possible states that can be reached from the start state of N along the e arrows. Changing yo' to be El{90}) achieves this cffect. We have now completed the construction of the DFA ! that simulates the NFA N. The construction of M obviously works correctly. At every step in the com- putation of Mon an input, it clearly enters a state that corresponds to the subset of states that N coull be in at that point. Thus our proof is complete. If the construction used in the preceding proof were more complex we would need to prove that it works as claimed. Usually such proofs proceed by induction on the number of steps of the computation. Most of the constructions that we use in this book are straightforward and so do not require such a correctness proof. An example of a more complex construction that we do prove correct appears in the proof of Theorem 1.54. Theorem 1.39 states that every NFA can be converted into an equivalent DFA. Thus nondeterministic finite automata give an altemative way of characterizing the regular languages. We state this fact as a corollary of Theorem 1.39