GeneralizedNondeterministicFiniteAutomaton.md (1170B)
1 # Generalized Nondeterministic Finite Automaton 2 3 **Source:** Theory of Computation 4 5 **Chapter:** 1 6 7 **Definition:** Generalized nondeterministic finite automaton (GNFA) are NFAs where the transitions may have regular expressions as labels. 8 9 By this definition we see that GNFAs can read in blocks of symbols, not just one as is the case with NFAs and DFAs. 10 11 GNFAs are useful because they can be used as an intermediary when converting DFAs to equivalent regular expressions. 12 13 DFA -> GNFA -> Regular Expression 14 15 --- 16 17 We can easily convert a DFA into a GNFA in the special form. We simply add a new start state with an ε arrow to the old start state and a new accept state with ε arrows from the old accept states. If any arrows have multiple labels (or if there are multiple arrows going between the same two states in the same direction), we replace each with a single arrow whose label is the union of the previous labels. Finally, we add arrows labeled ∅between states that had no arrows. This last step won’t change the language recognized because a transition labeled with ∅ can never be used. From here on we assume that all GNFAs are in the special form.