THEOREM 1.39 Every Now we need to consider the e aos. Io do so, We set up an xtra bit of noration. For any state R of M, e define E R) to be the collection of states that can be reached from members of R by going only alonge arrows, including the members of R themselves. Formally,for R Qlet finite automaton has an equivalent deterministic finite E(R) l can he reached from R by traveling along 0 or more e arrows) 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. 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 o(r, a) by E((r,a)) achieves this effect. Thus Recall the "reader would you simulate the NFA if you were pretending to be a DFA? What do you need to keep track ofas the input string is processed? In the examples of NFAs, you kept track of the various branches of the o 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 s automaton strategy for desi gning finite automsta. HoW Additionally, we need to modify the start state of W to mow thefingers ini- tially to all possible statn be eached from he sart state of N along the e arrows Changing qo' to be E(lg)achieves this effeet. We have now computation by placing a finger completed the consrruction of the DFA M that simulares the NFA N The construction of M obviously works correctly. At e puzation of of states that N could be in at that point. Thus our proof is complete. very step in the com- on an input, i clearly enters a state that corresponds to the subset 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 accep function. We can discuss this Theorcin 1.39 states that every NFA can le converted into an uivalent DFA. Thus nondeterministic fnite automata give an alternative way of characterizing the regular languages. We state this fact as a corollary of Theorem 1.39 t states of the DFA, and what will be its transition more easily after setting up some formal notati PROOF Let N-(Q, , , go. F) be the NFA recognizing some language A We construct a DFA M-(Q', , , %, F') recognizing A. B construction, let's first consider the easier case wherein N has no arrows. Later we take the e arrows into account. e doing thefull 2. Use the construction given in Theorem 1.39 to convert the following two nonde- terministic finite automata to equivalent deterministic finite automata Every state of M is a set of states of N. Recall that P(Q) is the set of subsets of Q 2. For R E Q' anda E , let 5"(R, a)-(q Ql q E (r,a) for some r E R} If R is a state of M, 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 reR M starts in the state corresponding to the collection containing just the start state of N 4. F'-{ R E Q,1 R contains n accept state of N } The machine M accepts if one of the possible states that N could be in at this point is an accept state lhe notation U (r, a) means: the union of the sets (na) for each possible r in R. Show your work (including intermediate results)