Generalized finite automaton

A finite directed automaton whose edge labels are regular expressions rather than individual letters. A path accepts concatenations of words in its successive labels, with choices over all accepting paths combined by union.

To remove an internal state $k$, replace each surviving label by $R_{ij}\cup R_{ik}(R_{kk}{)}^{\ast }{R}_{kj}$. The added term accounts for entering $k$, traversing its loop any number of times, and leaving it. Fresh initial and final states allow all old states to be eliminated, producing a regular expression for the same language.