A regular expression is easy for a human to write, but a computer cannot "run" (a + b)*abb directly on an input. A finite automaton, on the other hand, is trivial to run: read a symbol, follow an arrow. So every regex tool, from grep to the lexer inside a compiler, does the same thing first: it converts the regular expression into an automaton.
In Regular Expressions we stated Kleene's theorem: regular expressions and finite automata describe the same languages. This chapter proves the first half of it with a construction you can apply mechanically in an exam.
Every regular expression R can be converted into an ε-NFA N with L(N) = L(R). The standard method, Thompson's construction, builds N by induction on the structure of R, using one small "gadget" per operator.
We will learn the gadgets, build the ε-NFA for (a + b)*abb step by step, convert it to a DFA with the subset construction and minimise it. We will also see quick "by inspection" constructions and an ε-free method. Every machine in this chapter was simulated and compared with its regular expression on all strings up to length 10.
The Idea: Build Small Machines, Then Glue
A regular expression is built from atoms (∅, ε, a) using +, concatenation and *. So we only need:
a machine for each atom, and
a way to combine machines for R1 and R2 into machines for R1 + R2, R1R2 and R1*.
The glue is the ε-transition from Epsilon-NFA & Epsilon-Closure: a free arrow that lets us connect machines without changing what they read.
To make gluing easy, every machine N(R) that Thompson's construction produces keeps three promises (invariants):
It has exactly one start state and exactly one accepting state.
No arrow enters the start state, and no arrow leaves the accepting state.
Each state has at most two outgoing arrows (either one symbol arrow, or up to two ε-arrows).
Because of these promises we can treat each N(R) as a box with one way in (i) and one way out (f).
Thompson's Construction: The Gadgets
Basis
R = ε : (i) --ε--> ((f))
R = a : (i) --a--> ((f))
R = ∅ : (i) ((f)) no arrow at all, so nothing is acceptedHere (i) is the new start state and ((f)) the new accepting state.
Union: R = R1 + R2
ε +---------+ ε
.---->| N(R1) |-----.
/ +---------+ v
(i) ((f))
\ +---------+ ^
'---->| N(R2) |-----'
ε +---------+ εNew start i with ε-arrows into both machines; both old accepting states get ε-arrows to a new accepting state f (and stop being accepting). The machine can guess which branch to take: exactly the meaning of "R1 or R2". Adds 2 states.
Concatenation: R = R1R2
+---------+ +---------+
(i)-->| N(R1) (x) N(R2) |-->((f))
+---------+ +---------+
accepting state of N(R1) and start state of N(R2) are merged into xThe start of N(R1) is the new start, the accept of N(R2) is the new accept, and the accepting state of N(R1) is merged with the start state of N(R2). Adds no states (in fact it saves one). Some books instead join them with an ε-arrow; that is also correct, it just gives one extra state.
Star: R = R1*
ε (go round again)
.-----------------.
v |
(i) --ε--> (s) N(R1) ... (t) --ε--> ((f))
\ ^
'------------------ε---------------'
(skip: zero copies)Four ε-arrows: i → s (enter), t → f (leave), t → s (repeat), i → f (zero repetitions, so ε is accepted). Adds 2 states.
Why the extra states? It is tempting to just make the start state accepting and loop back to it. That breaks when R1* is later glued into a bigger machine: an arrow back into a start state can create paths that the regular expression does not allow. The fresh i and f keep every gadget sealed.
Size of the result
Each operand or operator adds at most two states, so if R has n symbols and operators in total, N(R) has at most 2n states and, since each state has at most two outgoing arrows, at most 4n transitions. The construction is linear in the size of the regex, which is why tools use it.
Worked Example: (a + b)*abb
This is the classic example from the Dragon Book (Aho, Lam, Sethi, Ullman), and the numbering below follows it so you can compare with your textbook. Build from the inside out:
Step | Sub-expression | What is added |
|---|---|---|
1 | a | 2 –a→ 3 |
2 | b | 4 –b→ 5 |
3 | a + b | new start 1 with 1 –ε→ 2, 1 –ε→ 4; new accept 6 with 3 –ε→ 6, 5 –ε→ 6 |
4 | (a + b)* | new start 0 and accept 7: 0 –ε→ 1, 6 –ε→ 7, 6 –ε→ 1 (repeat), 0 –ε→ 7 (skip) |
5 | (a + b)*a | 7 –a→ 8 (accept of the left part merged with start of a) |
6 | (a + b)*ab | 8 –b→ 9 |
7 | (a + b)*abb | 9 –b→ 10; 10 is the final accepting state |
ε
.-----------------------.
| ε a ε |
v .-->2--->3-----. |
0 --ε--> 1 --+ +--> 6 --ε--> 7 --a--> 8 --b--> 9 --b--> ((10))
| '-->4--->5-----' ^
| ε b ε |
'--------------------ε--------------------'Transition table (→ marks the start state, * the accepting state):
State | a | b | ε |
|---|---|---|---|
→ 0 | – | – | {1, 7} |
1 | – | – | {2, 4} |
2 | {3} | – | – |
3 | – | – | {6} |
4 | – | {5} | – |
5 | – | – | {6} |
6 | – | – | {1, 7} |
7 | {8} | – | – |
8 | – | {9} | – |
9 | – | {10} | – |
* 10 | – | – | – |
11 states, while the bound allows up to 2 × 10 = 20 (the expression has 5 symbols and 5 operators: +, *, and three concatenations).
Running it on "babb"
Simulate with sets of states: take the ε-closure, read a symbol, take the ε-closure again.
start ECLOSE{0} = {0, 1, 2, 4, 7}
read b move = {5} ECLOSE = {1, 2, 4, 5, 6, 7}
read a move = {3, 8} ECLOSE = {1, 2, 3, 4, 6, 7, 8}
read b move = {5, 9} ECLOSE = {1, 2, 4, 5, 6, 7, 9}
read b move = {5, 10} ECLOSE = {1, 2, 4, 5, 6, 7, 10} contains 10 => ACCEPTFrom the ε-NFA to a DFA
Now apply the subset construction from Epsilon-NFA & Epsilon-Closure: each DFA state is the ε-closure of a set of NFA states.
Step 1: ε-closures we need
q | ECLOSE(q) |
|---|---|
0 | {0, 1, 2, 4, 7} |
3 | {1, 2, 3, 4, 6, 7} |
5 | {1, 2, 4, 5, 6, 7} |
8, 9, 10 | just themselves |
Step 2: build DFA states on demand
DFA state | NFA states | move on a → ECLOSE | move on b → ECLOSE |
|---|---|---|---|
A | {0, 1, 2, 4, 7} | {3, 8} → B | {5} → C |
B | {1, 2, 3, 4, 6, 7, 8} | {3, 8} → B | {5, 9} → D |
C | {1, 2, 4, 5, 6, 7} | {3, 8} → B | {5} → C |
D | {1, 2, 4, 5, 6, 7, 9} | {3, 8} → B | {5, 10} → E |
E | {1, 2, 4, 5, 6, 7, 10} | {3, 8} → B | {5} → C |
Where the sets come from: from any set, reading a can only use the arrows 2 –a→ 3 and 7 –a→ 8, so the move is a subset of {3, 8}; reading b uses 4 –b→ 5, 8 –b→ 9 and 9 –b→ 10. E contains NFA state 10, so E is the only accepting DFA state.
DFA state | a | b |
|---|---|---|
→ A | B | C |
B | B | D |
C | B | C |
D | B | E |
* E | B | C |
Step 3: minimise
A and C have identical rows (a → B, b → C) and both are non-accepting, so they are equivalent (see DFA Minimization). Merging them gives the 4-state minimal DFA, which simply tracks "how much of abb have I just seen":
State | Meaning | a | b |
|---|---|---|---|
→ A | no useful progress | B | A |
B | just saw a | B | D |
D | just saw ab | B | E |
* E | just saw abb | B | A |
So the full pipeline is: regex → (Thompson) ε-NFA → (subset construction) DFA → (minimisation) minimal DFA. This is exactly the pipeline of lexer generators like lex/flex.
The Exam Shortcut: Building an NFA by Inspection
Thompson's machines are large because they are designed for a computer. By hand, you can usually write a small NFA directly using three patterns:
Regex piece | Draw it as |
|---|---|
R1R2 | the two pieces in series |
R1 + R2 | two parallel paths between the same pair of states |
(a + b)* in the middle or at the ends | a self-loop labelled a, b on one state |
Example 1: (a + b)*abb. A loop on the start state for (a + b)*, then a chain for abb:
a,b
↻
→ q0 --a--> q1 --b--> q2 --b--> ((q3))4 states instead of 11, no ε-moves. It accepts the same language as the Thompson machine (checked on all strings up to length 10).
Example 2: a(a + b)*b + b.
a,b
↻
→ q0 --a--> q1 --b--> ((q2))
\ ^
'--------b--------'State | a | b |
|---|---|---|
→ q0 | {q1} | {q2} |
q1 | {q1} | {q1, q2} |
* q2 | ∅ | ∅ |
Be careful with self-loops when a star is followed or preceded by other parts. The danger is putting two different stars on the same state. For a*b*, a single state with loops on a and b would accept ba, which is wrong. Use two states instead: q0 (accepting) with a loop on a, q1 (accepting) with a loop on b, and an arrow q0 –b→ q1. Once a b has been read the machine is in q1, where no a can be read any more. When in doubt, fall back to Thompson's rules, which are always correct.
An ε-free Method: The Position Automaton
There is a second classic construction (due to Glushkov, and used by the Dragon Book's "direct" regex-to-DFA method) that produces an NFA with no ε-moves and exactly one state per symbol occurrence plus a start state.
Number the symbol occurrences in (a + b)*abb as positions: a1, b2, a3, b4, b5. Then compute:
first = positions that can start a string: {1, 2, 3}.
last = positions that can end a string: {5}.
follow(p) = positions that can come right after p.
Position p | Symbol | follow(p) | Why |
|---|---|---|---|
1 | a | {1, 2, 3} | inside the star: repeat (1, 2) or leave it (3) |
2 | b | {1, 2, 3} | same |
3 | a | {4} | the a of abb is followed by the first b |
4 | b | {5} | then the last b |
5 | b | { } | end of the expression |
The NFA has states 0 (start) and 1 to 5. From 0 there is an arrow to each position in first; from p there is an arrow to each position in follow(p); each arrow into position q is labelled with q's symbol. Accepting states = last (plus 0 if the regex accepts ε).
State | a | b |
|---|---|---|
→ 0 | {1, 3} | {2} |
1 | {1, 3} | {2} |
2 | {1, 3} | {2} |
3 | – | {4} |
4 | – | {5} |
* 5 | – | – |
Subset construction on this gives the DFA states {0}, {1, 3}, {2}, {2, 4}, {2, 5}: the same shape as A, B, C, D, E above, and again {0} and {2} merge to give the 4-state minimal DFA. The compiler-design version of this method (with an end marker # and the functions nullable, firstpos, lastpos, followpos computed on a syntax tree) builds the DFA without ever drawing an NFA.
Comparing the Methods
Method | Output | Size | Best for |
|---|---|---|---|
Thompson's construction | ε-NFA, one start and one accept | at most 2n states | proofs, programs, guaranteed correctness |
By inspection | small NFA (often no ε) | smallest, but no fixed rule | quick exam answers |
Position (Glushkov) automaton | ε-free NFA | (number of symbol occurrences) + 1 states | direct regex-to-DFA in lexers |
Any of the above + subset construction | DFA | can be exponential in the worst case | when a deterministic machine is needed |
Common Mistakes
Star with no skip arrow. Without i –ε→ f, the machine for R* does not accept ε.
Star with no repeat arrow. Without t –ε→ s, R* behaves like ε + R.
Looping back into a shared start state. Shortcut machines that reuse states for two different stars accept extra strings (a*b* drawn on one state accepts ba).
Forgetting to take the ε-closure after a move during subset construction, or forgetting the closure of the start state.
Marking the wrong DFA states as accepting. A DFA state is accepting if it contains any NFA accepting state.
Expecting the same state count as your book. Different books glue concatenation differently (merge vs ε-arrow), so counts can differ by a few states. The language is what matters.
GATE-Style Questions
Q1. Using Thompson's construction (concatenation by merging), how many states does the ε-NFA for a* have? And for (a + b)*?
a*: the atom a has 2 states and star adds 2, so 4. (a + b)*: two atoms (4 states), union adds 2 (6), star adds 2, so 8 (states 0 to 7 in our worked example).
Q2. What is the minimum number of states in a DFA for (a + b)*abb?
4: the states record whether the string seen so far ends with nothing useful, a, ab or abb.
Q3. In the subset construction for the Thompson NFA of (a + b)*abb, which DFA state is reached from the start on input "ab"?
Start A = {0, 1, 2, 4, 7}; on a we reach B = {1, 2, 3, 4, 6, 7, 8}; on b we reach D = {1, 2, 4, 5, 6, 7, 9}. So D, the state that remembers "just saw ab".
Q4. For R1 + R2, why not simply merge the start states of the two machines instead of adding a fresh start state?
For arbitrary NFAs, merging is unsafe when an arrow comes back into a start state. Example: draw (ab)* as one accepting state s with s –a→ t and t –b→ s, and draw b as u –b→ ((v)). If s and u are merged, the string abb is accepted (s –a→ t –b→ s –b→ v), yet abb is in neither (ab)* nor b. The loop back into s let the machine cross from one branch into the other.
Thompson's own sub-machines never have arrows entering their start state, so for them a merge would happen to be harmless. The fresh start state is still used so that every gadget has the same sealed shape (one entry, one exit, at most two outgoing arrows per state) and the construction works by one uniform rule, with no special cases to check.
Q5. A regex has 6 symbol occurrences. How many states does its position (Glushkov) automaton have?
7: one per position plus the start state.
Summary
Every regular expression can be converted to an ε-NFA, which is half of Kleene's theorem.
Thompson's construction uses one gadget per atom and operator. Each gadget has one start state (no incoming arrows) and one accepting state (no outgoing arrows).
Union and star each add 2 states and ε-arrows. Concatenation merges the accept state of the first machine with the start state of the second. The result has at most 2n states.
For (a + b)*abb: Thompson gives 11 states, subset construction gives 5 DFA states (A to E), and minimisation gives 4.
By hand, small NFAs can be drawn by inspection, but avoid sharing one state between two stars.
The position automaton gives an ε-free NFA with one state per symbol occurrence plus a start state.
The reverse direction, automaton → regular expression, is the topic of the next chapter, Finite Automata to Regular Expression (Arden's Theorem).