= Solution
Use <state elimination for finite automata> on a <generalized finite automaton>, whose directed <edges> are labelled by <regular expressions>. Add a fresh initial state $s$ with an $\varepsilon$-edge to the old initial state and a fresh final state $f$ with $\varepsilon$-edges from all old accepting states. Every missing <edge> has label $\varnothing$, the <empty language>; parallel <edges> are merged by <union>. The label $\varepsilon$ denotes the language containing just the <empty word>.
When eliminating a state $k$, replace the label on each surviving <edge> $i\to j$ by
$$
\boxed{R_{ij}\ \cup\ R_{ik}(R_{kk})^*R_{kj}.}
$$
Here juxtaposition means <concatenation of formal languages>, and the <Kleene star> allows zero or more traversals of the loop at $k$. Then delete $k$ and its incident <edges>. Eliminate every original state; the remaining $s\to f$ label is a <regular expression> for exactly the accepted <formal language>. The update accounts for paths avoiding $k$ and paths entering $k$, looping there any number of times, and leaving it.
Back to article page
