Generalized nondeterministic finite automaton
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 generalized nondeterministic finite automaton (GNFA) can be defined as a 5-tuple: (S, Σ, T, s, a)
- S is a finite set of states
- Σ is a finite set of symbols
- T : (S -{a}) × (S - {s}) → R
- s ∈ S is the start state
- a ∈ S is the accept state
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}.