hello can you please help me with this problem because I am struggling can you please help me I have add the theorem because I don't understand the theorem at all.Can you please draw something visual so I can understand it better. THEOREM 1.39Every nondeterministic finite automaton has an equivalent deterministic finiteautomaton.PROOF IDEA If a language is recognized by an NFA, then we must show theexistence of a DFA that also recognizes it. The idea is to convert the NFA into anequivalent DFA that simulates the NFA.Recall the "reader as automaton" strategy for designing finite automata, Howwould you simulate the NFA if you were pretending to be a DFA? What do youneed 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 fingeron each state that could be active at given points in the input. You updated thesimulation by moving, adding, and removing fingers according to the way theNFA operates. All you needed to keep track of was the set of states having fingerson them.If k is the number of states of the NFA, it has 2 subsets of states. Each subsetcorresponds to one of the possibilities that the DFA must remember, so the DFAsimulating the NFA will have 2" states. Now we need to figure out which willbe the start state and accept states of the DFA, and what will be its transitionfunction. We can discuss this more easily after setting up some formal notation,PROOF Let N = (QE, d, go, F) be the NFA recognizing some language A.We construct a DFA M = (Q',E, 8', qo', F) recognizing A. Before doing the fullconstruction, let's first consider the easier case wherein N has no e arrows. Laterwe take the e arrows into account1. Q' P(Q).Every state of M is a set of states of N. Recall that P(Q) is the set ofsubsets of Q.2. For RE Q' and a E, let 6'(R, a) = {g € Q] ged(r, a) for some re K},If R is a state of M, it is also a set of states of N. When M reads a symbola in state R, it shows where a takes each state in R. Because cach state maygo to a set of states, we take the union of all these sets. Another way towrite this expression is&'(Ra)=$(r.a).4TER3.90 (90).M starts in the state corresponding to the collection containing just thestart state of N.4. F(REQ R contains an accept state of N).The machine M accepts if one of the possible states that I could be in atthis point is an accept state.The notation (r, a) means: the union of the sets 8(r, a) for each possible r in It.PGRNow we need to consider the e arrows. To do so, we set up an extra bit ofnotation. For any state R of M, we define E(R) to be the collection of statesthat can be reached from members of R by going only along e arrows, includingthe members of R themselves. Formally, for RC Q letE(R) (qq can be reached from R by traveling along 0 or more & arrows).Then we modify the transition function of M to place additional fingers on allstates that can be reached by going along e arrows after every step. Replacings(r,a) by E(8(r, a)) achieves this effect. Thus(R. a) (ge Ql qE E(S(r, a)) for some r = R}.8Additionally, 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 alongthe e arrows. Changing qo' to be E({0}) achieves this effect. We have nowcompleted 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 M on an input, it dearly enters a state that corresponds to the subsetof states that N could be in at that point. Thus our proof is complete.Theorem 1.39 states that every NFA can be converted into an equivalent DFA.Thus nondeterministic finite automata give an alternativo way of characterizingthe regular languages, We state this fact as a corollary of Theorem 1.39.mondial 1.16 Use the construction given in Theorem 1.39 to convert the following two nonde-terministic finite automata to equivalent deterministic finite automata.12(a)a, b

The question revolves around Theorem 1.39, which states that every non deterministic finite…

Answered: 1.16 Use the construction given in…

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE