REGULAR EXPRSSION TO FINITE AUTOMATA:

THOMPSON’S CONSTRUCTION METHOD

CONSTRUCTION OF FINITE AUTOMATA FOR REGULAR EXPRSSION

If R is a regular expression over Σ representing regular language L, then there exists an NFA M
with ε-transitions such that M accepts L

Let L(R) denotes the set or language represented by R.

Basis:

There are three parts of the basis, shown in Figure 1.

In part (a) we see how to handle the regular expression R which is ε. The language of the
automation is easily seen to be L(R) = {ε}, since the only path from the start state to an accepting
state is labeled ε.
In part (b) we can see the construction for regular expression R which is Φ. Clearly there are no
paths from start state to accepting state, so L(R) = Φ is the language for this automation.
Finally, part (c) gives the automation for a regular expression R which is a where a Є Σ. The
language L(R) of this automation evidently consists of the one string a, which is also {a}.

ε
OR

Figure 1 (a): NFA M1 which accepts the regular language L = {ε}

OR

Figure 1 (b): NFA M2 which accepts the regular language L = Φ

Figure 1 (c): NFA M3 which accepts the regular language L = {a}

1
Induction:

The three parts of the induction are shown in Figure 3.2.

Case i:
The expression is R1+R2 for some smaller expressions R1 and R2. Then the automation of Figure
3.2(a) serves. That is, starting at the new start state, we can go to the start state of either the
automation for R1 or the automation for R2 through ε-arc. We then reach the accepting state of
one of these automata, following a path labeled by some string in L(R 1) and L(R2), respectively.
Once we reach the accepting state of the automation for R1 or R2, we can follow one of the ε-arcs
to the accepting state of the new automation. Thus the language of the new automation in Figure
2(a) L(R1+R2) is L(R1)∪L(R2).

Case ii:
The expression is R1R2 for some smaller expressions R1 and R2. The automation for the
concatenation is shown in Figure 3.2(b). Let us note that the start state of the first automation
becomes the start state of the whole, and the accepting state of the second automation becomes
the accepting state of the whole. The idea is that the only paths from start to the accepting state
go first through the automation for R1, where it must follow a path labeled by a string in L(R1)
and then through the automation for R2, where it follows a path labeled by a string in L(R2).
Thus, the paths in the automation of Figure 2(b) are all and only those labeled by strings in
L(R1)L(R2). That is, L(R1+R2) = L(R1) L(R2).

Case iii:
The expression is R* for some smaller expression R. Then we use the automation of Figure 2(c).
That automation allows us to go either

 Directly from the start state to the accepting state along a path labeled ε. That path lets us
accept ε, which is in L(R*) no matter what expression R is.
 To the start state of the automation for R, through that automation one or more times, and
then to the accepting state. This set of paths allows us to accept strings in L(R),
L(R)L(R), L(R)L(R)L(R), and so on, thus covering all strings in L(R*) except perhaps ε,
which was covered by the direct arc to the accepting state mentioned previously.

2
 NFA accepting L(R1)

ε ε

ε
ε

NFA accepting L(R2)

Figure 2 (a): NFA M4 which accepts the regular language L(R1+R2)

NFA accepting L(R1) NFA accepting L(R2)

Figure 2 (b): NFA M5 which accepts the regular language L(R1R2)

Figure 2 (c): NFA M6 which accepts the regular language L(R1*)

3
Example:

Let us convert the regular expression (0+1)*0 to an ε-NFA using Thompson’s Construction:

Our first step is to construct automation for 0+1. We use two automata constructed according to
Figure 1(c), one with label 0 on the arc and one with label 1. These two automata are then
combined using the union construction of Figure 2(a). n. The result is shown in Figure 3(a).

Next, we apply to Figure 3(a) the star construction of Figure 2(c). This automation is shown in
Figure 3(b).

The last step involves applying the concatenation construction of Figure 2(b). We connect the
automation of Figure 3(b) to another automation designed to accept only the string 0. This
automation is another application of the basis construction of Figure 1(c) with label 0 on the arc.
Let us note that we must create a new automation to recognize 0; we must not use the automation
for 0 that was part of Figure 3(a). The complete automation is shown in Figure 3(c).

0
ε ε

ε 1 ε

(a)
ε

0 ε
ε ε
ε

ε ε
1

(b)

4
 ε

0 ε
ε ε
ε ε 0

ε ε
1

, ε

(c)

Figure 3: ε-NFA constructed for regular expression (0+1)*0

5
 Example:

Let us convert the regular expression (a+b)*.a.b.b to an ε-NFA using Thompson’s Construction:

2 a 4
ε ε ε ε ε
0 1 6 7 8
ε
3 b 5 ε a

9
ε ε

10 b

11

12

13

Figure 4: ε-NFA constructed for regular expression (a+b)*abb