Theoretical Aspects of Lexical Analysis/Exercise 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: <graph> digraph nfa {

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

} </graph>

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: <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 2 node [shape=circle,fixedsize=true,width=0.2,fontsize=10]; start -> 0 0 -> 1 [label="a"] 0 -> 2 [label="b"] 1 -> 2 [label="b"] 2 -> 1 [label="a"] 2 -> 2 [label="b"] fontsize=10 //label="DFA for ((ε|a)b)*" } </graph> Given the minimization tree to the right, the final minimal DFA is: <graph> digraph dfamin { { node [shape=circle style=invis] start } rankdir=LR; ratio=0.5 node [shape=doublecircle,fixedsize=true,width=0.3,fontsize=10]; 02 node [shape=circle,fixedsize=true,width=0.2,fontsize=10]; 1 start -> 02 02 -> 1 [label="a"] 02 -> 02 [label="b"] 1 -> 02 [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}" -> "{1}" [label="NF",fontsize=10] "{0, 1, 2}" -> "{0, 2}" [label=" F",fontsize=10] "{0, 2}" -> "{0,2} " [label=" a,b",fontsize=10] fontsize=10 //label="Minimization tree" } </graph>