Theoretical Aspects of Lexical Analysis/Exercise 1

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

• (a|b)*

Solution

NFA

The following is the result of applying Thompson's algorithm.

<graph>

digraph nfa {

rankdir=LR; ratio=0.5 node [shape=doublecircle,fixedsize=true,width=0.2,fontsize=10]; 7 node [shape=circle,fixedsize=true,width=0.2,fontsize=10];

 0 -> 1 
 1 -> 2 
 1 -> 4
 2 -> 3 [label="a",fontsize=10]
 4 -> 5 [label="b",fontsize=10]
 3 -> 6
 5 -> 6
 6 -> 1
 6 -> 7

 0 -> 7

 fontsize=10
 label="NFA for (a|b)*"

} </graph>