NFA or DFA to regular expression
State elimination removes the states of an automaton one at a time and keeps every path through them as an expression on the remaining edges. When one edge is left, its label is the answer.
Each step lights up the state being eliminated and shows the edges that were rewritten. The regular expression appears at the last step.
Add a new start state and a new accepting state
An ε-move from the new start to q0, and ε-moves from every accepting state to the new accepting state. These two are never eliminated.
Pick a state to eliminate
States with few paths through them go first — that keeps the expression short.
Reconnect its neighbours directly
For every pair p → state → r, add to the edge p → r the expression: (p to state)(loop on state)*(state to r).
Read the last edge
When only the new start and accepting states remain, the label between them describes the whole language.
Why is my expression so long?
State elimination is correct but not clever: the expression can grow quickly with the number of states, and different elimination orders give different (equivalent) answers. Minimizing the DFA first usually helps a lot.
Is the expression simplified?
Lightly: ∅ and ε are removed where they change nothing, duplicate alternatives are merged, and ε + rr* becomes r*. It is not guaranteed to be the shortest possible expression.
How do I convert my own machine?
Open the simulator, draw a DFA or NFA, and choose Convert → To regex in the dock.