a generalized NFA

An ordinary NFA labels each transition with a single symbol or with ε. A generalized NFA loosens this: each transition may be labeled with an entire regular expression. It is the working surface for state elimination, a kind of scaffolding that lets you collapse a complicated automaton down to one regular expression without losing track of the language along the way.

Concretely, a GNFA reads a chunk of the input whenever it takes a transition: an arrow labeled with the expression E can be followed by consuming any string in L(E). To make state elimination clean, GNFAs are usually kept in a normal form: exactly one start state with no incoming arrows, exactly one accept state distinct from the start with no outgoing arrows, and between every other ordered pair of states a single arrow (possibly labeled ∅ to mean 'no transition'). In this form, removing one interior state at a time and merging its bypass paths keeps the GNFA well-formed until only the start-to-accept arrow remains.

The GNFA is a conceptual tool, not a model you would study for its own power; it recognizes exactly the regular languages, the same as an ordinary NFA, because every regular-expression label could in principle be expanded back into states and single-symbol transitions. Its value is purely as the bookkeeping device that makes the finite-automaton-to-regular-expression direction of Kleene's theorem tidy and provably correct.