Equivalence of Regular Expressions and Finite Automata

Regular expressions and finite automata define the same class of languages. One direction builds an $\varepsilon$-NFA from an expression (Thompson's construction). The other eliminates states from a DFA (or NFA) until a single regular expression remains. Together with the subset construction, this closes the loop: RE $\Leftrightarrow$ $\varepsilon$-NFA $\Leftrightarrow$ NFA $\Leftrightarrow$ DFA.

The working tasks are building an NFA from an RE, an RE from a small DFA, and proving a language regular by exhibiting either description.

For a language $L \subseteq \Sigma^*$, the following are equivalent:

Thompson's construction builds an $\varepsilon$-NFA with exactly one start state and one accept state, and with no edges into the start or out of the accept, by composing fragments:

The resulting NFA has $O(|r|)$ states. Convert to a DFA by subset construction if needed.

To get an RE from an automaton:

Arden's lemma is the algebraic twin: if $Q = \alpha Q + \beta$ and $\varepsilon \notin L(\alpha)$, then $Q = \alpha^* \beta$.

Different elimination orders yield different but equivalent expressions.

Thompson for concatenation, union and star follows the fragment table. State count: every symbol, $\varepsilon$ or $\emptyset$ fragment has 2 states, union and star add 2 new states each, and concatenation adds none, so the NFA has at most $2|r|$ states, where $|r|$ counts symbols and operators. Textbooks differ on whether concatenation merges the two glued states, so a question asking for an exact Thompson state count must fix the convention.

State elimination makes polynomially many algebraic label updates, but explicitly expanded expressions can grow exponentially. Elimination is manageable by hand on small machines; expression size matters to the actual running time.

By induction on the expression: each fragment accepts exactly $L(r)$, and composing fragments preserves the inductive semantics of $+$, concatenation and star because $\varepsilon$-edges only glue without reading input.

When $q$ is removed, every path $i \to q \to \cdots \to q \to j$ that looped on $q$ a total of $k \ge 0$ times becomes a single RE edge $R_{iq} R_{qq}^* R_{qj}$. Summing with the old $i \to j$ paths leaves the language of labels from start to accept unchanged.

Solving $X = AX + B$ for languages with $\varepsilon \notin A$ gives the unique solution $X = A^* B$. Proof: unfold $X = A(AX+B)+B = A^2 X + AB + B = \cdots$, and the $\varepsilon \notin A$ condition prevents infinite descent from hiding extra strings.

Build fragments for $a$, $b$, union, star, then concatenate a, b, b. With the $\varepsilon$-glued concatenation of the fragment table the NFA has 14 states: 2 for each of the five symbol occurrences, 2 for the union and 2 for the star. The machine accepts strings ending with abb. Subset construction followed by minimization gives the 4-state DFA that tracks progress towards abb.

DFA for "even number of 0s": states $A$ (start, accept) and $B$; alphabet $\{0,1\}$; $A \xrightarrow{1} A$, $A \xrightarrow{0} B$, $B \xrightarrow{0} A$, $B \xrightarrow{1} B$. $A$ means "even 0s so far", $B$ means "odd".

Eliminate $B$: the path $A \xrightarrow{0} B \xrightarrow{1^*} B \xrightarrow{0} A$ contributes $0 1^* 0$, and the direct loop contributes $1$. The new self-loop on $A$ is $1 + 01^*0$, and since $A$ is both start and accept the answer is $(1 + 01^*0)^*$.

One wrong edge changes the language. If $B \xrightarrow{0} B$ and $B \xrightarrow{1} A$ instead, eliminating $B$ gives $(1 + 00^*1)^*$, which is "empty, or ends in 1". The two machines agree on 1, 00 is in the first language only, and 01 is in the second only. Always check the edges out of the eliminated state before writing the loop label.

$(0+1)^* 01 (0+1)^*$. Thompson yields an $\varepsilon$-NFA; subset construction and minimization give a 3-state DFA: "no progress", "last symbol was 0" and the accepting sink "seen 01". Three states are necessary: prefixes $\varepsilon$, 0, and 01 are pairwise distinguishable. Continuation 1 distinguishes the first two; the empty continuation distinguishes 01 from either of them.

Thompson produces an epsilon-NFA with a chain: read a, then loop on a+b via star fragment, then read b. After subset construction and removing unreachable sets, the DFA tracks: have we read the leading a? are we in the middle? have we just closed with b? Membership: a string is accepted iff it starts with a, ends with b, and has length at least 2. Checks: ab yes; aab yes; aaabbb yes; a no; b no; ba no.

To show $(0+1)^* 01 (0+1)^* = (0+1)^* 0 (0+1)^* 1 (0+1)^*$: the second form asks for some 0 followed later by some 1. Take the last 0 before that 1; the symbol after it is a 1, so the factor 01 occurs. The converse is immediate. The automaton method gives the same answer: both expressions minimize to the same 3-state DFA of Example 3.

Use the DFA of Deterministic Finite Automata (residues $q_0, q_1, q_2$, start and accept $q_0$). Eliminate $q_2$ first: it is entered only from $q_1$ on 0, loops on 1, and leaves to $q_1$ on 0, so $q_1$ gains the loop $0 1^* 0$. Now eliminate $q_1$: it is entered from $q_0$ on 1, loops on $0 1^* 0$, and returns to $q_0$ on 1, so $q_0$ gains the loop $1 (0 1^* 0)^* 1$. Together with the 0-loop on $q_0$:

11 (3), 110 (6) and 1001 (9) match; 10 (2) and 111 (7) do not. Eliminating in the order $q_1$ first gives a longer but equivalent expression.

Write one equation per state for the set of strings that lead to it ($\varepsilon$ for the start state):

The second equation has the form $B = B\,1 + A\,0$; the right-sided Arden rule ($X = X\alpha + \beta$ with $\varepsilon \notin L(\alpha)$ gives $X = \beta \alpha^*$) yields $B = A\,0\,1^*$. Substitute: $A = \varepsilon + A(1 + 0 1^* 0)$, so $A = (1 + 0 1^* 0)^*$, matching the elimination answer. Since $A$ is the only accepting state, this is the language.

Arden's condition matters. If $\varepsilon\in L(\alpha)$, uniqueness is no longer guaranteed: the equation may have multiple solutions. For $\alpha=\varepsilon$ and $\beta\subsetneq\Sigma^*$, every $X\supseteq\beta$ is a solution; if $\beta=\Sigma^*$, only $X=\Sigma^*$ is possible.

A right-linear grammar has rules $A \to wB$ or $A \to w$ with $w \in \Sigma^*$; a left-linear one has $A \to Bw$ or $A \to w$. Both generate exactly the regular languages. From a DFA: one variable per state, a rule $p \to a\,q$ for each edge $\delta(p,a) = q$, and $p \to \varepsilon$ for each accepting $p$. For the reverse direction, first normalize to single-terminal rules $A\to aB$, $A\to a$, with optional unit/epsilon rules. Then use one state per normalized variable plus a final state; general word-labelled edges for longer $w$ must instead be expanded into paths with intermediate states.

Mixing is not allowed. A grammar that uses right-linear and left-linear rules together can be non-regular: $S \to aT$, $T \to Sb \mid b$ is "linear" but generates $\{a^n b^n \mid n \ge 1\}$.

IMPERATIVE RULE. When asked only for an NFA, stop after Thompson. When asked for a DFA, always finish subset construction (and minimize if the question says minimal).

Common misconceptions.