Theoretical Aspects of Lexical Analysis/Exercise 5

Compute the non-deterministic finite automaton (NFA) by using Thompson's algorithm. Compute the minimal deterministic finite automaton (DFA). The alphabet is Σ = { a, b }. Indicate the number of processing steps for the given input string.

• G = { ab, ab*, a|b }, input string = abaabb

Solution

NFA

The following is the result of applying Thompson's algorithm. State 3 recognizes the first expression (token T1); state 8 recognizes token T2; and state 14 recognizes token T3.

<graph> digraph nfa {

    { node [shape=circle style=invis] s }
 rankdir=LR; ratio=0.5
 node [shape=doublecircle,fixedsize=true,width=0.2,fontsize=10]; 3 8 14
 node [shape=circle,fixedsize=true,width=0.2,fontsize=10];

 s -> 0

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

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

 0 -> 9
 9 -> 10
 9 -> 12
 10 -> 11 [label="a",fontsize=10]
 12 -> 13 [label="b",fontsize=10]
 11 -> 14
 13 -> 14
 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, 4, 9, 10, 12	0
0	a	2, 5, 11	2, 5, 6, 8, 11, 14	1 (T2)
0	b	13	13, 14	2 (T3)
1	a	-	-	-
1	b	3, 7	3, 6, 7, 8	3 (T1)
2	a	-	-	-
2	b	-	-	-
3	a	-	-	-
3	b	7	6, 7, 8	4 (T2)
4	a	-	-	-
4	b	7	6, 7, 8	4 (T2)

Graphically, the DFA is represented as follows: <graph> digraph dfa { { node [shape=circle style=invis] s } rankdir=LR; ratio=0.5 node [shape=doublecircle,fixedsize=true,width=0.2,fontsize=10]; 1 2 3 4 node [shape=circle,fixedsize=true,width=0.2,fontsize=10]; s -> 0 0 -> 1 [label="a",fontsize=10] 0 -> 2 [label="b",fontsize=10] 1 -> 3 [label="b",fontsize=10] 3 -> 1 [label="a",fontsize=10] 3 -> 4 [label="b",fontsize=10] 4 -> 4 [label="b",fontsize=10] fontsize=10 //label="DFA for (a|b)*abb(a|b)*" } </graph> The minimization tree is as follows. Note that before considering transition behavior, states are split according to the token they recognize. <graph> digraph mintree { node [shape=none,fixedsize=true,width=0.3,fontsize=10] "{0, 1, 2, 3, 4}" -> "{0}" [label="NF",fontsize=10] "{0, 1, 2, 3, 4}" -> "{1, 2, 3, 4}" [label=" F",fontsize=10] "{1, 2, 3, 4}" -> "{3}" [label=" T1",fontsize=10] "{1, 2, 3, 4}" -> "{1, 4}" [label=" T2",fontsize=10] "{1, 2, 3, 4}" -> "{2}" [label=" T3",fontsize=10] "{1, 4}" -> "{1}" //[label=" T3",fontsize=10] "{1, 4}" -> "{4}" [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 final states {1, 4}). Given the minimization tree, the final minimal DFA is exactly the same as the original DFA (all leaf sets are singular).