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)*abb(a|b)*

Solution

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

NFA

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

Determination table

In α∈Σ move(In, α) ε-closure(move(In, α)) In+1 = ε-closure(move(In, α)) - - 0 0, 1, 2, 4, 7 0 0 a 3, 8 1, 2, 3, 4, 6, 7, 8 1 0 b 5 1, 2, 4, 5, 6, 7 2 1 a 3, 8 1, 2, 3, 4, 6, 7, 8 1 1 b 5, 9 1, 2, 4, 5, 6, 7, 9 3 2 a 3, 8 1, 2, 3, 4, 6, 7, 8 1 2 b 5 1, 2, 4, 5, 6, 7 2 3 a 3, 8 1, 2, 3, 4, 6, 7, 8 1 3 b 5, 10 1, 2, 4, 5, 6, 7, 10, 11, 12, 14, 17 4 4 a 3, 8, 13 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16, 17 5 4 b 5, 15 1, 2, 4, 5, 6, 7, 11, 12, 14, 15, 16, 17 6 5 a 3, 8, 13 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16, 17 5 5 b 5, 9, 15 1, 2, 4, 5, 6, 7, 9, 11, 12, 14, 15, 16, 17 7 6 a 3, 8, 13 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16, 17 5 6 b 5, 15 1, 2, 4, 5, 6, 7, 11, 12, 14, 15, 16, 17 6 7 a 3, 8, 13 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16, 17 5 7 b 5, 10, 15 1, 2, 4, 5, 6, 7, 10, 11, 12, 14, 15, 16, 17 8 8 a 3, 8, 13 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16, 17 5 8 b 5, 15 1, 2, 4, 5, 6, 7, 11, 12, 14, 15, 16, 17 6

Graphically, the DFA is represented as follows:

DFA

The minimization tree is as follows:

Minimization tree

Given the minimization tree above, the final minimal DFA is as follows:

Minimal DFA