In the [[theory of computation]], a '''generalized nondeterministic finite state machine''', also known as '''expression automaton'''
or '''generalized nondeterministic finite automaton (GNFA)''' is aan [[nondeterministic finite state machine|NFA]] where each transition is 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. There are several differences between a standard finite state machine and a generalized nondeterministic finite state machine. A gNFA must have only one start state and one accept state, and these cannot be the same state, where as a NFA or DFA both may have several accept states, and the start state can be an accept state. A gNFA must have only one transition between any two states, where as a NFA or DFA both allow for numerous transitions between states. In a gNFA, a state has a single transition to every state in the machine, although often it is a convention to ignore the transitions that are labelled with the empty set when drawing generalized nondeterministic finite state machines.
