Chapter 12 of 34

Regular Expression to Finite Automata

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:

  1. a machine for each atom, and

  2. 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 accepted

Here (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 x

The 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  =>  ACCEPT

From 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).