Theoretical Aspects of Lexical Analysis/Exercise 4

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

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]; 17
 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

 7 -> 8 [label="a",fontsize=10]
 8 -> 9 [label="b",fontsize=10]
 9 -> 10 [label="b",fontsize=10]

 10 -> 11 
 11 -> 12 
 11 -> 14
 12 -> 13 [label="a",fontsize=10]
 14 -> 15 [label="b",fontsize=10]
 13 -> 16
 15 -> 16
 16 -> 11
 16 -> 17
 10 -> 17

 fontsize=10
 //label="NFA for (a|b)*abb(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, 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, 15	1, 2, 4, 5, 6, 7, 11, 12, 14, 15, 16, 17	6
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

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]; 4 5 6 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 -> 3 [label="b"] 2 -> 1 [label="a"] 2 -> 2 [label="b"] 3 -> 1 [label="a"] 3 -> 4 [label="b"] 4 -> 5 [label="a"] 4 -> 6 [label="b"] 5 -> 5 [label="a"] 5 -> 6 [label="b"] 6 -> 5 [label="a"] 6 -> 6 [label="b"] fontsize=10 //label="DFA for (a|b)*abb(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.4,fontsize=10]; 456 node [shape=circle,fixedsize=true,width=0.2,fontsize=10]; start -> 02 02 -> 1 [label="a"] 02 -> 02 [label="b"] 1 -> 1 [label="a"] 1 -> 3 [label="b"] 3 -> 1 [label="a"] 3 -> 456 [label="b"] 456 -> 456 [label="a"] 456 -> 456 [label="b"] fontsize=10 //label="DFA for (a|b)*abb(a|b)*" } </graph>

The minimization tree is as follows. As can be seen, the states are indistinguishable. <graph> digraph mintree { node [shape=none,fixedsize=true,width=0.3,fontsize=10] "{0, 1, 2, 3, 4, 5, 6}" -> "{0, 1, 2, 3}" [label="NF",fontsize=10] "{0, 1, 2, 3, 4, 5, 6}" -> "{4, 5, 6}" [label=" F",fontsize=10] //"{0, 1, 2, 3}" -> "{0, 1, 2, 3} " [label=" a",fontsize=10] "{0, 1, 2, 3}" -> "{0, 1, 2}" "{0, 1, 2, 3}" -> "{3} " [label=" b",fontsize=10] "{0, 1, 2}" -> "{0, 2} " "{0, 1, 2}" -> "{1} " [label=" b",fontsize=10] fontsize=10 //label="Minimization tree" } </graph> The tree expansion for non-splitting sets has been omitted for simplicity ("a" transition for non-final states and the {0, 2} "a" and "b" transitions. The final states are all indistinguishable, regarding either "a" or "b" transitions.