Drawtomata / Finite automaton to regular expression

Finite automaton to regular expression

Draw a DFA or NFA above and press FA → RE. Drawtomata turns it into a generalized transition graph and removes states one at a time, showing the new edge labels after each removal.

State elimination

  1. Make sure the start state has no incoming edges and there is a single final state, adding new ones joined by λ-moves if needed.
  2. Pick a state q to remove. For every pair of neighbours p → q → r, replace the path with one edge labelled R(p,q) R(q,q)* R(q,r), joined by + to any edge p → r that is already there.
  3. Repeat until only the start and final states remain. The label of the last edge is the regular expression.

The order of elimination changes how the expression looks, not the language it describes. The result is checked against the automaton.

Questions

Why is my answer different from the book’s?

Different elimination orders give different, equally correct expressions. If the language matches, the answer is right.