how to do the regex thing, but actually

(As usual, ensure)

• start state has no in-arrows
  add new state state with $\varepsilon$-transition to old
• singular accept state and has no out-arrows
  add new accept state with $\varepsilon$-transitions from all olds

Then, eliminate non-accept/start states one by one, until only start and accept are left.

Eliminating a state:
For all pairs of in-arrows and out-arrows, add a new equivalent “bypass” arrow – the concatenation of the in and the out.
If the state has a self-loop, then sandwich that (with a Kleene star) in the concatenation.

Observe that the number of new arrows to add is #ins $\times$ #outs, so eliminate states with the least in$\times$out first!!!

That’s it.

---

Example

Consider the following 6-state state diagram.

---

$\rm{Q_2}$ has 2 ins and 2 outs; to eliminate it would require 4 additional bypass arrows.
Meanwhile, $\rm{Q_0}$ has only 2$\times$1 = 2, so let’s eliminate $\rm{Q_0}$ first.

The two in-out pairs are
$\text{start} \xrightarrow{\varepsilon} \rm{Q_0} \xrightarrow{b} \rm{Q_1}$
$\rm{Q_2} \xrightarrow{a} \rm{Q_0} \xrightarrow{b} \rm{Q_1}$

We therefore add the bypass arrows
$\text{start} \xrightarrow{b} \rm{Q_1}$
$\rm{Q_2} \xrightarrow{ab} \rm{Q_1}$

And we can now safely kill $\rm{Q_0}$ (and its attached arrows).

We now have

Oh no! we have two parallel arrows from $\rm{Q_2}$ to $\rm{Q_1}$, $\xrightarrow{\rm b}$ and $\xrightarrow{\rm ab}$?!
Well, they can be union’d into $\xrightarrow{\rm b \ |\ ab}$:

---

Now we repeat the process. $\rm{Q_3}$ (or $\rm{Q_2}$) now has the least in$\times$out, so let’s eliminate it.

The 2 in-out pairs:
$\rm{Q_1} \xrightarrow{a} \rm{Q_3} \xrightarrow{a} \rm{Q_2}$
$\rm{Q_1} \xrightarrow{a} \rm{Q_3} \xrightarrow{\varepsilon} \text{end}$

Turns into:
$\rm{Q_1} \xrightarrow{aa} \rm{Q_2}$
$\rm{Q_1} \xrightarrow{a} \text{end}$

So,

And union’ing $\xrightarrow{\rm b}$ and $\xrightarrow{\rm aa}$,

---

Now, eliminate $\rm{Q_2}$.

It only has 1 in-out pair:
$\rm{Q_1} \xrightarrow{b\ |\ aa} \rm{Q_2} \xrightarrow{b\ |\ ab} \rm{Q_1}$

So we add
$\rm{Q_1} \xrightarrow{(b\ |\ aa) (b\ |\ ab)} \rm{Q_1}$
(remember to add parentheses)

---

Only $\rm{Q_1}$ is left 👀.

It has 1 in and 1 out, but has a self-loop!
$\text{start} \xrightarrow{b} \underset{\mathclap{\overset{\small\circlearrowright}{(b|aa)(b|ab)}}}{\rm{\normalsize Q_1}} \xrightarrow{a} \text{end}$

We do the same as before, but sandwich the self-loop along a kleene star:
$\text{start} \xrightarrow{\small b \ {\normalsize(}(b|aa)(b|ab){\normalsize)}^* \ a} \text{end}$

Which gives

…and $\ \rm b \,\big( (b\,|\,aa)(b\,|\,ab) \big)^*\, a \space$ is precisely the equivalent regex!