Wiki**3

Problem

Use Thompson's algorithm to build the NFA for the following regular expression. Build the corresponding DFA and minimize it.

• ((ε|a)b)*

Solution

The non-deterministic finite automaton (NFA), built by applying Thompson's algorithm to the regular expression ((ε|a)b)* is the following:

Applying the determination algorithm to the above NFA, the following determination table is obtained:

In	α∈Σ	move(In, α)	ε-closure(move(In, α))	In+1 = ε-closure(move(In, α))
-	-	0	0, 1, 2, 3, 4, 6, 8	0
0	a	5	5, 6	1
0	b	7	1, 2, 3, 4, 6, 7, 8	2
1	a	-	-	-
1	b	7	1, 2, 3, 4, 6, 7, 8	2
2	a	5	5, 6	1
2	b	7	1, 2, 3, 4, 6, 7, 8	2

Graphically, the DFA is represented as follows: Given the minimization tree to the right, the final minimal DFA is:	The minimization tree is as follows.