3/24/2021 0 Comments Nfa To Dfa
Verification of reactive systems: formal methods and algorithms. Springer. pp. 210212. ISBN 978-3-540-00296-3.
![]() However, if the NFA has n states, the resulting DFA may have up to 2 n states, an exponentially larger number, which sometimes makes the construction impractical for large NFAs. In contrast, to simulate an NFA, one needs to keep track of a set of states: all of the states that the automaton could reach after seeing the same prefix of the input, according to the nondeterministic choices made by the automaton. If, after a certain prefix of the input, a set S of states can be reached, then after the next input symbol x the set of reachable states is a deterministic function of S and x. Therefore, the sets of reachable NFA states play the same role in the NFA simulation as single DFA states play in the DFA simulation, and in fact the sets of NFA states appearing in this simulation may be re-interpreted as being states of a DFA. Such an automaton may be defined as a 5-tuple ( Q,, T, q 0, F ), in which Q is the set of states, is the set of input symbols, T is the transition function (mapping a state and an input symbol to a set of states), q 0 is the initial state, and F is the set of accepting states. The corresponding DFA has states corresponding to subsets of Q. ![]() The transition function of the DFA maps a state S (representing a subset of Q ) and an input symbol x to the set T ( S, x ) T ( q, x ) q S, the set of all states that can be reached by an x -transition from a state in S. A state S of the DFA is an accepting state if and only if at least one member of S is an accepting state of the NFA. However, many states of the resulting DFA may be useless as they may be unreachable from the initial state. An alternative version of the construction creates only the states that are actually reachable. Van Noord recognizes three possible ways of incorporating this closure computation in the powerset construction: 5. This version, also discussed by Hopcroft and Ullman, 6 is straightforward to implement, but impractical for automata with large numbers of -moves, as commonly arise in natural language processing application. Its alphabet consists of the two symbols 0 and 1, and it has -moves. A transition from 1,2,3 by input symbol 0 must follow either the arrow from state 1 to state 2, or the arrow from state 3 to state 4. Additionally, neither state 2 nor state 4 have outgoing -moves. Nfa To Dfa Full DFA ConstructedTherefore, T (1,2,3,0) 2,4, and by the same reasoning the full DFA constructed from the NFA is as shown below. It can be represented by an ( n 1) -state NFA, but it requires 2 n DFA states, one for each n -character suffix of the input; cf. It converts the input DFA into an NFA for the reverse language, by reversing all its arrows and exchanging the roles of initial and accepting states, converts the NFA back into a DFA using the powerset construction, and then repeats its process. Its worst-case complexity is exponential, unlike some other known DFA minimization algorithms, but in many examples it performs more quickly than its worst-case complexity would suggest. Introduction to Automata Theory, Languages, and Computation. Reading Massachusetts: Addison-Wesley. ISBN 0-201-02988-X. Verification of reactive systems: formal methods and algorithms. Springer. pp. 210212. ISBN 978-3-540-00296-3.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |