Conversions between regular expressions and finite automata
How to convert between regular expressions and finite automata (NFA/DFA): constructions, correctness ideas, and worked examples (Thompson, GNFA/state-elimination, Arden).
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Engineers use conversions between regular expressions and finite automata when designing lexical analysers, hardware controllers, and pattern-matchers: a regular expression is an easy specification, while a finite automaton is what a compiler or hardware implements. Knowing both directions lets you prove a language is regular and produce an implementation from a specification.
Key ideas
Definitions (simple, exact):
- Alphabet: a finite non-empty set Σ of symbols. Example: Σ = {a, b}.
- String: a finite sequence of symbols from Σ. Empty string is denoted ε.
- Language: a set of strings over Σ.
- Regular expression (RE): a formula built from ∅ (empty set), ε, symbols in Σ, and operators union (written |), concatenation, and Kleene star (*). The RE denotes a language by the usual inductive rules:
- ∅ denotes the empty language.
- ε denotes {ε}.
- a (for a in Σ) denotes {a}.
- If R and S are REs, then (R|S) denotes L(R) ∪ L(S); (R S) denotes concatenation L(R)L(S); (R*) denotes Kleene closure L(R)*.
- Finite automaton (FA): a 5-tuple (Q, Σ, δ, q0, F). If δ is single-valued it is a deterministic finite automaton (DFA); if δ is set-valued it is a nondeterministic finite automaton (NFA). An ε-NFA allows transitions labeled ε.
- Kleene's theorem (exact statement): A language L over Σ is regular (i.e., described by some RE) if and only if L is accepted by some finite automaton (equivalently, by some NFA or by some DFA). Assumption: automata may use ε-transitions when convenient; equivalence of NFA and DFA is assumed (subset construction).
Two standard constructive conversions (exam-level detail):
From a regular expression to an NFA — Thompson's construction (algorithm):
- For basic atoms create tiny NFAs:
- For symbol a: make two states p and q; add transition p --a--> q; p is start, q is final.
- For ε: p --ε--> q.
- For ∅: create two states p and q with no transition between them; p is start, q is final (so no path exists, and the language accepted is ∅).
- For operators, combine fragments with new start and new final states using ε-transitions:
- Union R|S: create new start s and new final f; add ε from s to starts of R and S; add ε from finals of R and S to f.
- Concatenation RS: connect final of R by an ε to start of S; start is start of R; final is final of S.
- Kleene star R*: create new start s and final f; add ε from s to start(R) and to f; add ε from final(R) back to start(R) and to f.
- End result: NFA with a single start and single accept state. For exams: draw fragments as small graphs and show how to join them with labeled ε arrows.
Correctness idea: prove by structural induction on the RE that the constructed NFA accepts exactly the language denoted by the RE.
- For basic atoms create tiny NFAs:
From a finite automaton to a regular expression — state-elimination / GNFA method (algorithm):
If starting from a DFA/NFA, first convert it to a GNFA (generalised NFA): a directed graph with a single start and a single accept state, and each ordered pair of states i -> j has exactly one edge labeled by a regular expression describing the set of strings consumed by that single edge from i to j (initially a single symbol, or ∅ if no transition).
If necessary, add a new start s with ε to old start, and a new final f with ε from each old final to f; make no other outgoing from f and no incoming to s.
Repeat: pick a state r that is neither s nor f to eliminate. Suppose there are states p and q with labels R_{p,r}, R_{r,r} (loop), R_{r,q}, and R_{p,q}. Replace R_{p,q} by R_{p,q} | (R_{p,r} (R_{r,r})* R_{r,q}). Remove r and all its incident edges. Continue until only s and f remain; the label on s->f is an RE for the language.
State-elimination order matters for compactness but not correctness. For exams, show the elimination step formula and give a few eliminations with updated labels.
Correctness idea: each elimination preserves the set of paths from s to f, because any path that used r is captured by concatenation and star formula.
Alternative algebraic method: use Arden's theorem to solve linear equations for state languages. Arden's theorem: if X = A X ∪ B and ε not in L(A), then X = A* B is the unique solution. This is useful to convert DFA to RE by writing one equation per state for the set of strings taking start to that state.
Remarks: NFA-to-DFA subset construction and DFA minimisation are separate topics but are commonly used before applying state-elimination for a cleaner automaton.
Diagrams to draw in answers (describe):
- For Thompson fragments: draw for each operator a small directed graph with labeled transitions; label start and final states with small circles, mark unique start with an incoming arrow and final with double circle.
- For GNFA elimination: draw full state diagram with edges labeled by REs; when eliminating a node, show the update formula and new label on each affected edge.
Formulas
L(R|S) = L(R) ∪ L(S) — union of languages; L(R|S) means language of regex R|S.
L(RS) = L(R) · L(S) — concatenation: set of uv with u in L(R), v in L(S).
L(R*) = (L(R))* — Kleene closure: union_{i≥0} L(R)^i.
If X = A X ∪ B and ε not in L(A) then X = A* B — Arden's theorem (X, A, B are language expressions). (Assumption: A, B are known REs/languages.)
State-elimination update: R_{p,q} := R_{p,q} | (R_{p,r} (R_{r,r})* R_{r,q}) — when eliminating state r in GNFA.
Notation: ε is the empty string; ∅ is empty language. Operator precedence: * binds tightest, concatenation next (left-associative), and | has the lowest precedence (left-associative); parentheses override. No SI units apply.
Worked examples
Example 1 — Convert RE (a|b)* a b b to an NFA (Thompson). Steps:
- Break RE into operators: ( (a|b)* ) concatenated with a then b then b.
- Build fragment for (a|b): start s1, end f1 with ε branching to 'a' fragment and 'b' fragment; join to a common final. Then apply Kleene star: add new start s2 and new final f2 with ε to s1 and to f2, and loop from f1 back to s1 with ε. (Draw: new start ->ε-> s1; s1 ->ε-> a-frag start and ->ε-> b-frag start; each atomic fragment is two states with one labeled edge; finals ->ε-> f1; f1 ->ε-> s1 and ->ε-> f2.)
- Concatenate the star-fragment with 'a' fragment: connect f2 ->ε-> start of 'a' fragment; similarly then connect final of that to start of next 'b' fragment, etc.
- Final NFA: list states and transitions. (For exam, draw the whole graph.)
Final answer (sketch): NFA has a single overall start and single accept; transitions are a mix of ε and labeled edges as per Thompson's rules. (I am confident about the construction; the precise picture should be drawn on the answer sheet.)
Example 2 — Convert DFA to RE by state-elimination. DFA: Σ={0,1}; language = strings ending with 01. DFA states: q0 (start), q1, q2 (accept). Transitions:
- q0 --0--> q1, q0 --1--> q0
- q1 --0--> q1, q1 --1--> q2
- q2 --0--> q1, q2 --1--> q0 (These implement 'most recent two symbols' memory.)
Steps (sketch):
- Add new start s with ε->q0 and new final f with ε from q2->f; remove accepting marks on q2.
- Convert edges to RE labels (single symbols as REs). No parallel edges initially.
- Eliminate q1 first. Compute new labels using R_{p,q} := R_{p,q} | (R_{p,q1} (R_{q1,q1})* R_{q1,q}). Carry out for all pairs p,q in {s,q0,q2,f}. (Show intermediate algebra.)
- Then eliminate q0; finally eliminate q2 to get RE on s->f.
Final simplified RE (after algebra) is: (0|1)* 0 1 which matches language of strings ending with 01. (For full-marks answer, show each elimination step algebraically; show simplifications of unions and concatenations.)
Example 3 — Use Arden's theorem quickly: For DFA with states q0 start, q1 accept, transitions q0 --a--> q1, q0 --b--> q0, q1 --a--> q1, q1 --b--> q0 (language: strings ending with a). Write equations for R0 (strings from q0 to accept q1) and R1 (strings from q1 to q1):
- R0 = b R0 | a R1
- R1 = a R1 | b R0 | ε (since q1 is accepting, ε is included when starting in q1). Solving: R1 = a* (b R0 | ε) = a* b R0 | a*, and substituting into R0 gives R0 = (b | a a* b)* a a*, which simplifies to (a|b)* a a* (strings ending with a). (Show algebraic steps in exam.)
I am reasonably sure of the example outcomes above, but please verify the intermediate algebra in Example 3.
Common mistakes
- Using Arden's theorem without checking the condition that ε not be in A.
- Mixing up ε (empty string) and ∅ (empty language) in constructions and proofs.
- Trying to eliminate start or final prematurely in state-elimination method.
- Not simplifying REs at each step, producing unnecessarily long answers and losing marks for clarity.
For your exam
Question types you will see:
- Definitions and short notes: define RE, NFA, GNFA, Kleene's theorem, Thompson construction.
- Derivations: prove correctness of Thompson construction by induction, or derive state-elimination update formula.
- Conversions: given an RE produce an NFA (draw diagram); given a small DFA produce an RE (show state elimination or Arden steps).
- Short proofs: show two automata are equivalent or prove a language is regular by giving an RE or FA.
What a full-marks answer includes:
- Clear definitions (bold/underlined terms if allowed), correct diagrams with start/accept markers, and transitions labeled.
- For constructions, list all states and transitions or clearly draw fragments and show how they join.
- For state-elimination, show the GNFA initial step, each elimination with updated labels and final RE; simplify the final RE.
- For algebraic solutions, cite Arden's theorem and check its conditions before using it.
Quick check
- State Thompson's construction idea for union in one sentence.
- Write the state-elimination update formula for replacing R_{p,q} when eliminating r.
- State Arden's theorem condition for using X = A* B as a solution.
Answers: 1) Create a new start and new final and connect start to the starts of the two sub-NFAs with ε and connect their finals to the new final with ε. 2) R_{p,q} := R_{p,q} | (R_{p,r} (R_{r,r})* R_{r,q}). 3) X = A X ∪ B has unique solution X = A* B provided ε not in L(A).
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?