Generalized nondeterministic finite state machine
From Wikipedia, the free encyclopedia
In the theory of computation, a generalized nondeterministic finite state machine, also known as expression automaton or generalized nondeterministic finite automaton (GNFA) is a NFA where each transition may be labeled with any regular expression. The GNFA reads blocks of symbols from the input which constitute a string as defined by the regular expression on the transition.
[edit] Formal definition
A GNFA can be defined as a 5-tuple, (S, Σ, T, s, a), consisting of
- a finite set of states (S);
- a finite set called the alphabet (Σ);
- a transition function (T : (S -{a}) × (S - {s}) → R);
- a start state (s ∈ S);
- an accept state (a ∈ S);
where R is the collection of all regular expressions over the alphabet Σ.
A DFA or NFA can easily be converted into a GNFA and then the GNFA can be easily converted into a regular expression by repeatedly collapsing parts of it to single edges until S = {s, a}. Similarly, GNFAs can be reduced to NFAs by changing regular expression operators into new edges until each edge is labelled with a regular expression matching a single string of length at most 1. NFAs, in turn, can be reduced to DFAs using the powerset construction. This shows that GNFAs recognize the same set of formal languages as DFAs and NFAs.
[edit] References
- Yo-Sub Han and Derick Wood. "The Generalization of Generalized Automata: Expression Automata." In: 9th International Conference on Implementation and Application of Automata, CIAA 2004, Kingston, Canada, July 22-24, 2004, Revised Selected Papers, LNCS 3317, pp. 156-166. doi:10.1007/b105090
[edit] External links
- A graphical description of GNFAs and the process of converting an NFA to a regular expression using GNFAs, can be found at [1]
