From Automaton to Regex: The GNFA Method

Converting an automaton to a regular expression runs the NFA-to-regex conversion the other way: build a generalized NFA (GNFA) whose transition labels are full regular expressions instead of single symbols, then eliminate states one at a time — folding each removed state's incoming and outgoing paths into a single new regex label — until only a start and accept state are left, connected by one edge. That edge's label is the answer.

Setting up the GNFA

Every automaton is first reshaped into GNFA form: a fresh start state ε-links to the original start, every original accept state ε-links to a fresh accept state, and any missing transition between two states is filled in with the "reject everything" regex ∅ so the machine is fully connected. From there, states are removed one by one (any order works; the resulting regex may just look different depending on the order).

Worked example: even number of 1s

This 2-state DFA accepts binary strings containing an even number of 1s (including zero).

Eliminating e1 (the non-start, non-accept-adjacent state isn't literally removable here since it's needed — this DFA is already minimal at 2 states, so state elimination folds directly into one edge): every excursion out of e0 through e1 and back corresponds to reading a 1, then any number of 0s, then another 1 that returns to e0 — that's the block 0*10*1. Any number of such excursions can happen, interleaved with runs of 0s that never leave e0 at all. That gives the closed form:

(0*10*1)*0*

Read it as: any number of "pairs of 1s with 0s scattered around them," followed by a trailing run of 0s — which is exactly "an even number of 1s total," since every accepted 1 is paired up.

Your turn