In the theory of computation, a generalized nondeterministic finite state machine or generalized nondeterministic finite automaton (GNFA) is a NFA where each transition may be labeled with any regular expression. The GNFA read blocks of symbols from the input which constitute a string as defined by the regular expression on the transition.
Formal definition
A GNFA can be defined as a 5-tuple: (S, Σ, T, s, a)
- a finite set of states (S)
- a finite set of symbols (Σ)
- 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 reducing the number of states until S = {s, a}.