FA to Regex Conversion: State Elimination with a Fully Worked Example

The state-elimination rule looks short, but one omitted loop, parallel edge, or epsilon connector changes the language. This guide makes the process mechanical with a GNFA ledger, one two-state DFA carried through every update, and a reverse elimination order as a cross-check. The machine accepts precisely the strings over {a,b} that end in a, so every algebraic step has a clear meaning and exact test strings you can verify by hand.

What FA-to-regex conversion preserves

Every DFA or NFA recognises a regular language, and some regular expression denotes that same language. Conversion changes the representation, not the set of accepted strings. The result is not unique, and the expression produced by a particular elimination order need not be the shortest one.

We will use empty-set for no path and epsilon for a path that consumes no input. The symbol + means union, juxtaposition means concatenation, and * means Kleene star. Precedence runs from star to concatenation to union, so add parentheses whenever an update could be misread.

Do not mix up the two directions. Regex-to-FA conversion builds a machine from an expression. FA-to-regex conversion removes states or solves language equations. The Theory of Computation study hub gives the broader context for both.

Turn the automaton into a GNFA first

Prepare the machine in this order:

1. Add a fresh start state s with only s --epsilon--> q0.

2. Add a fresh final state f with q1 --epsilon--> f.

3. Ensure that s has no incoming edges and f has no outgoing edges.

4. Combine parallel edges with union.

5. Treat every missing edge as empty-set, even if the drawing omits it.

When eliminating state k, update every surviving predecessor i and successor j by

R_ij(new) = R_ij(old) + R_ik(R_kk)*R_kj.

The two terms mean either follow the existing direct route, or enter k, travel around its loop zero or more times, and leave k. Before erasing a state, record R_kk, list every incoming and outgoing edge, update every incoming-outgoing pair, and merge each result with the old R_ij. Delete k only after that ledger is complete. Stop when only s and f remain. Their edge label is the required regex.

Worked DFA for strings ending in a

Use Q={q0,q1}, alphabet Sigma={a,b}, start state q0, and accepting set F={q1}.

State q0 means the input is empty or currently ends in b. State q1 means it currently ends in a. Therefore epsilon and b reject; a, ba, and abba accept; and abb rejects.

After adding s and f, freeze the initial labels: R_s,q0=epsilon, R_q0,q0=b, R_q0,q1=a, R_q1,q0=b, R_q1,q1=a, and R_q1,f=epsilon. Every other pair is empty-set. For a structured treatment of this machine and related methods, use the Theory of Computation / Automata Theory course.

Eliminate q0 and update every affected label

The incoming edges to q0 are s --epsilon--> q0 and q1 --b--> q0. Its loop is b, and its only outgoing edge to another surviving state is q0 --a--> q1. The affected pairs are therefore s to q1 and q1 to itself.

For the first pair, retain the existing missing route explicitly:

R_s,q1 = empty-set + epsilon(b)*a = b*a.

This label consumes any number of initial bs and then one a.

For the second pair, retain the existing a loop:

R_q1,q1 = a + b(b)*a = a+bb*a.

The first choice reads another a directly. The second leaves q1 on one b, stays at q0 for zero or more further bs, and returns on a. After deleting q0, the complete reduced GNFA has states {s,q1,f} and exactly these edges: s --b*a--> q1, a q1 loop labelled a+bb*a, and q1 --epsilon--> f. All other labels remain empty-set.

Eliminate q1, read the regex, and test it

Apply the rule once more:

R_s,f = empty-set + (b*a)(a+bb*a)*epsilon = b*a(a+bb*a)*.

This is the direct conversion result. The prefix b*a reaches an accepting condition once. Each repetition of the loop returns to a string that ends in a.

For a, choose b*=epsilon and zero loop repetitions. For ba, the initial b* consumes b. For abba, the prefix consumes a, then one loop block bb*a consumes bba. The strings epsilon, b, and abb cannot match because the expression always contributes a final a.

At the language level, the compact form is (a+b)*a. It is not textually identical to b*a(a+bb*a)*, but both denote every string over {a,b} that ends in a.

Why another elimination order gives another correct regex

Now eliminate q1 first. Its loop is a, so the updated q0 loop is

b + a(a)*b = b+aa*b,

and the new edge from q0 to f is

a(a)*epsilon = aa*.

The edge s --epsilon--> q0 remains unchanged. Eliminating q0 next gives

R_s,f = epsilon(b+aa*b)*aa* = (b+aa*b)*aa*.

The expressions (b+aa*b)*aa*, b*a(a+bb*a)*, and (a+b)*a look different but preserve the same language. Elimination order may change size and appearance, so compare answers with state meanings and short witnesses, not visual similarity.

Arden's theorem offers another route. If p is the start, f is accepting, p --b--> f, and f has an a loop, let X_f describe labels on paths from p to f. The equation X_f=b+X_fa gives X_f=ba*, matching direct elimination.

Conversion traps in objective questions

An objective question may ask for one updated R_ij, the expression after a named elimination order, a missing union term, or the solution to a small Arden equation. To compare candidates, test epsilon, a, b, ba, abb, and abba against both the machine and the regex.

KnowledgeGate has 20+ published FA to Regex Conversion questions for practice. Use the live Theory of Computation MCQs hub to practise these patterns, without treating availability in a practice bank as evidence of exam frequency.

The short version and the next practice step

Add fresh s and f. Merge parallel labels. Eliminate one internal state at a time with R_ij + R_ik(R_kk)*R_kj. Stop when the sole s -> f label remains. Here the result is b*a(a+bb*a)*, equivalent to (a+b)*a.

Rebuild the ledger without looking, then check a, ba, abba, epsilon, b, and abb against both forms. Continue with the Theory of Computation course for focused automata study, Zero to Hero Complete CS Course for a wider core-CS route, or CS Fundamentals for Exams and Placements for subject-wise browsing.