Theoretical Aspects of Lexical Analysis/Exercise 4

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
{{{2}}}

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

Determination table
{{{2}}}

Graphically, the DFA is represented as follows:

DFA
{{{2}}}

The minimization tree is as follows:

Minimization tree

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

Minimal DFA
{{{2}}}