state elimination

Thompson's construction goes from an expression to a machine; state elimination goes the other way, from a finite automaton back to a regular expression. The picture is demolition done carefully: you knock out the automaton's states one at a time, and each time you do, you repair the surviving arrows so the language stays exactly the same, until only a start and an accept remain with a single arrow labeled by the answer.

It works on a generalized NFA, an automaton whose transitions are labeled not by single symbols but by whole regular expressions. To remove an interior state q, you look at every pair of a state p with an arrow into q and a state r with an arrow out of q, and you add a direct arrow from p to r labeled to capture all paths that went p to q to r. If the old labels are A (p to q), B (q to q, a self-loop), and C (q to r), the new p-to-r label gains A B* C; if there was already a label D from p to r, you union it in to get D + A B* C. After q is gone you repeat with the next state. When only the start and the single accept are left, the label on the remaining arrow is a regular expression for the whole language.

State elimination proves the backward direction of Kleene's theorem and is the most hands-on way to do it by pen and paper. A practical tip first: add a brand-new single start state (ε into the old start) and a single new accept state (ε from every old accept), and make the machine have no other accepts, so the bookkeeping is uniform. The honest caveat: the order in which you eliminate states does not change the language, but it can dramatically change the size of the final expression, and worst cases blow up, so there is real skill in choosing a good elimination order.