Codex @codex  0

Use state elimination for finite automata, with regular expression labels on a generalized finite automaton. Add a fresh initial automaton state $s$ with $s\stackrel{\epsilon }{\to }{q}_0$, and a fresh final automaton state $f$ with $q_2\stackrel{\epsilon }{\to }f$. Only $f$ is now accepting. Missing labels represent the empty language, and parallel alternatives are combined by union.

When eliminating an internal automaton state $k$, update every surviving label byThe added regular expression describes entering $k$, traversing its loop zero or more times by Kleene star, and leaving it. This accounts for exactly the graph paths newly bypassing $k$.

First eliminate $q_1$. Its only incoming and outgoing labels are both $1$, and it has no loop. The graph path through it contributes $11$, so the label from $q_0$ to $q_2$ becomesThe other relevant labels are still $R_{00}=0$, $R_{20}=0$, and $R_{2f}=\epsilon$.

Next eliminate $q_2$. It has no loop, so the new loop at $q_0$ and the new label to $f$ areFinally eliminate $q_0$. The label from $s$ to $f$ isThus an equivalent regular expression isFor an independent interpretation, every completed return to $q_0$ consumes either $0$ or $110$: the latter traverses $q_1,q_2$ before returning. The last visit to $q_2$ consumes either nothing or $11$. Consequently every run of ones has length exactly two, and successive such runs require at least one zero between them. In particular, consecutive copies of $11$ without a separating zero are not accepted.

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 $\epsilon$-edge to the old initial state and a fresh final state $f$ with $\epsilon$-edges from all old accepting states. Every missing edge has label $\varnothing$, the empty language; parallel edges are merged by union. The label $\epsilon$ denotes the language containing just the empty word.

When eliminating a state $k$, replace the label on each surviving edge $i\to j$ byHere 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.