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 {

    { node [shape=circle style=invis] start }
 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];
 start -> 0
 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>

DFA

Determination table for the above NFA:

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

Graphically, the DFA is represented as follows:

<graph> digraph dfa {

    { node [shape=circle style=invis] start }
 rankdir=LR; ratio=0.5
 node [shape=doublecircle,fixedsize=true,width=0.2,fontsize=10]; 0 1 2
 node [shape=circle,fixedsize=true,width=0.2,fontsize=10];
 start -> 0
 0 -> 1 [label="a"]
 0 -> 2 [label="b"]
 1 -> 1  [label="a"]
 1 -> 2  [label="b"]
 2 -> 1 [label="a"]
 2 -> 2 [label="b"]
 fontsize=10
 //label="DFA for (a|b)*"

} </graph>

The minimization tree is as follows

<graph> digraph mintree {

 node [shape=none,fixedsize=true,width=0.2,fontsize=10]
 " {0, 1, 2}" -> "{}" [label="NF",fontsize=10]
 " {0, 1, 2}" -> "{0, 1, 2}" [label="F",fontsize=10]
 "{0, 1, 2}" -> "{0, 1, 2} " [label="a,b",fontsize=10]
 fontsize=10
 //label="Minimization tree"

} </graph>