Regex and Finite Automata Equivalence: Conversions, Worked Examples and Exam Traps

A regular expression and a finite automaton can look unrelated even when they describe exactly the same strings. In conversion questions, that gap makes symbol-pushing fragile and easy to mistrust. The reliable approach is to preserve the language at every step, so we will build one complete regex-to-NFA-to-DFA example, reverse an FA into a regex, and apply concrete equivalence checks from CS fundamentals.

What regex and finite-automata equivalence actually means

Fix an alphabet Sigma. A regular expression R denotes a language L(R), while an NFA or DFA M recognises a language L(M). Saying R and M are equivalent means exactly this:

L(R) = L(M)

Their symbols, shape and number of states need not look alike. Regular expressions, epsilon-NFAs, NFAs and DFAs all describe exactly the regular languages, so conversion is possible in both directions. The pumping lemma helps establish regular-language boundaries, but it is not a conversion algorithm.

Keep precedence fixed while reading every expression: star binds first, concatenation second and union last. Therefore (0|1)*101 means any binary prefix followed by the exact suffix 101. It does not mean 0 | 1*101.

The conversion map to remember

The forward route is:

regex -> epsilon-NFA -> DFA -> optional minimum DFA

In Thompson's construction, a symbol contributes one labelled edge. Union adds an epsilon split and join, concatenation connects fragments with an epsilon edge, and star adds both an epsilon bypass and an epsilon return. Epsilon-closure followed by subset construction removes nondeterminism without changing the language. The guide to DFA, NFA and subset construction develops those reachable-set mechanics further.

The reverse route is FA -> GNFA -> regex. Add a new start and a new accepting state, label absent edges with the empty language, combine parallel edges by union, then eliminate intermediate state k using:

Rij <- Rij | Rik(Rkk)*Rkj

Arden's theorem offers another route through regular-language equations. Whichever route you choose, the invariant is the same: every step must preserve all accepted strings, not merely agree on a few samples.

Worked example: convert (0|1)*101 to an NFA

Use one language throughout the forward conversion:

R = (0|1)*101
Sigma = {0,1}
L(R) = {w101 | w in {0,1}*}

A compact direct NFA uses start state q0 and only accepting state q3:

The loop at q0 consumes an arbitrary binary prefix. Its extra branch on 1 guesses where the final 101 starts. For 110101, the full state-set trace is:

{q0} -1-> {q0,q1} -1-> {q0,q1} -0-> {q0,q2} -1-> {q0,q1,q3} -0-> {q0,q2} -1-> {q0,q1,q3}

The set contains q3 after all six symbols, so the NFA accepts. For 1010, the trace ends at {q0,q2}. The branch that reached q3 after 101 cannot consume the last 0, so the machine rejects. As boundary checks, 101 is accepted, while epsilon, 10 and 1011 are rejected.

Determinise the NFA and verify the same language

Subset construction produces only four reachable subsets. A DFA state is accepting exactly when its subset contains q3.

The empty subset is unreachable because every reachable set retains q0. Now 110101 follows D0 -1-> D1 -1-> D1 -0-> D2 -1-> D3 -0-> D2 -1-> D3, so it is accepted. Input 1010 ends with D0 -1-> D1 -0-> D2 -1-> D3 -0-> D2, so it is rejected.

The four states are also minimal. D3 is accepting and the other states are not. Suffix 1 distinguishes D2 from both D0 and D1, while suffix 01 distinguishes D1 from D0. Equivalence follows from the subset invariant: after every input prefix, the DFA state contains exactly the NFA states reachable on that prefix.

Reverse direction: turn a small FA into a regex

Consider an automaton M over {a,b}. State p is the start, r is accepting, and its only transitions are p -a-> p, p -b-> r and r -b-> r. Its strings contain zero or more a symbols followed by one or more b symbols.

For a GNFA, add new start s with s -epsilon-> p and new final f with r -epsilon-> f. Eliminate p first. The new label from s to r is:

epsilon(a)*b = a*b

Eliminating r then gives:

a*b(b)*epsilon = a*bb*

Thus the equivalent regex is exactly a*bb*. Input aabbb follows p -a-> p -a-> p -b-> r -b-> r -b-> r and matches the regex. Input aba reaches r after ab but has no move on the last a; it also fails the regex. Replacing the result with a*b* is wrong because that expression also admits epsilon and aaa.

How to prove equivalence and find a counterexample

There are three dependable proof routes. Use a semantics-preserving construction such as subset construction, reduce both descriptions to minimal DFAs and compare them up to state renaming, or build a DFA for their symmetric difference and check whether any accepting state is reachable.

For example, compare R1=(0|1)*101 with R2=(0|1)*0101. String 101 belongs to L(R1) but not L(R2), so this one witness disproves equivalence. Testing 0101 alone proves nothing because both expressions accept it.

For two DFAs, form product states (x,y) and mark a pair accepting when exactly one component accepts. Breadth-first search from the paired start returns a shortest distinguishing string if a mismatch is reachable. If no mismatch is reachable, the DFAs are equivalent.

Exam-style traps and a reliable solving routine

Typical question formats ask you to choose an equivalent regex, complete a transition, calculate epsilon-closures, list reachable subsets, perform one GNFA elimination, or decide whether two machines accept the same language. The focused follow-on, Regex and FA Equivalence MCQs: 10 Solved PYQs, lets you apply these methods.

Use each trap as a correction cue:

• Following only q0 -1-> q1 and dropping q0 -> retain the whole set {q0,q1}.

• Accepting when q3 first appears during 1010 -> consume the full input; the final set is {q0,q2}.

• Treating epsilon as an alphabet symbol -> take an epsilon transition without consuming input.

• Reading (0|1)*101 as 0 | 1*101 -> apply precedence or retain the parentheses.

• Replacing a*bb* with a*b* -> test epsilon as a counterexample.

For a quick routine, write the alphabet and acceptance condition, parenthesise the regex, build the transition table, compute closures before moves, and retain only reachable subsets. Trace one accepted string and one boundary reject. Then seek a counterexample before starting a long proof. KnowledgeGate has 30+ published practice questions tagged to Regex & FA Equivalence, which is useful as a practice-pool cue.

Short version and the next practice step

Remember the chain: regex to epsilon-NFA by fragments, epsilon-NFA to DFA by closures and subsets, then DFA to regex by GNFA elimination. Equivalence means the same language, not the same drawing. Here, 110101 ends at D3, while 1010 ends at D2; the reverse example gives a*bb*, not a*b*.

Reconstruct the four-row table without looking, then test 101, 00101, 1010 and epsilon: accept, accept, reject, reject. Continue with Theory Of Computation / Automata Theory as the focused route, or Zero to Hero: Complete CS Course for broader multi-subject study.