Theoretical Aspects of Lexical Analysis/Exercise 9

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 = { a*, ba*, a|b* }, input string = aababb

NFA

The following is the result of applying Thompson's algorithm. State 4 recognizes the first expression (token T1); state 9 recognizes token T2; and state 17 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]; 4 9 17
 node [shape=circle,fixedsize=true,width=0.2,fontsize=10];

 s -> 0

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

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

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

} </graph>

DFA

Determination table for the above NFA:

In	α∈Σ	move(In, α)	ε-closure(move(In, α))	In+1 = ε-closure(move(In, α))
-	-	0	0, 1, 2, 4, 5, 10, 11, 13, 14, 16, 17	0 (T1)
0	a	3, 12	2, 3, 4, 12, 17	1 (T1)
0	b	6, 15	6, 7, 9, 14, 15, 16, 17	2 (T2)
1	a	3	2, 3, 4	3 (T1)
1	b	-	-	-
2	a	8	7, 8, 9	4 (T2)
2	b	15	14, 15, 16, 17	5 (T3)
3	a	3	2, 3, 4	3 (T1)
3	b	-	-	-
4	a	8	7, 8, 9	4 (T2)
4	b	-	-	-
5	a	-	-	-
5	b	15	14, 15, 16, 17	5 (T3)

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]; 0 1 2 3 4 5
 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="a",fontsize=10]
 2 -> 4 [label="a",fontsize=10]
 2 -> 5 [label="b",fontsize=10]
 3 -> 3 [label="a",fontsize=10]
 4 -> 4 [label="a",fontsize=10]
 5 -> 5 [label="b",fontsize=10]
 fontsize=10

} </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, 5}" -> "{}" [label="NF",fontsize=10]
 "{0, 1, 2, 3, 4, 5}" -> "{0, 1, 2, 3, 4, 5} " [label="  F",fontsize=10]
 "{0, 1, 2, 3, 4, 5} " -> "{0, 1, 3}" [label="  T1",fontsize=10]
 "{0, 1, 2, 3, 4, 5} " -> "{2, 4}" [label="  T2",fontsize=10]
 "{0, 1, 2, 3, 4, 5} " -> "{5}" [label="  T3",fontsize=10]
 "{0, 1, 3}" -> "{0}" //[label="  b",fontsize=10]
 "{0, 1, 3}" -> "{1,3}" [label="  b",fontsize=10]
 "{2, 4}" -> "{2}" //[label="  b",fontsize=10]
 "{2, 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" transitions for super-state {0, 1, 3}, and "a" and "b" transitions for super-state {1,3}).

Given the minimization tree, the final minimal DFA is as follows. Note that states 2 and 4 cannot be the same since they recognize different tokens.

<graph> digraph mindfa {

    { node [shape=circle style=invis] s }
 rankdir=LR; ratio=0.5
 node [shape=doublecircle,fixedsize=true,width=0.2,fontsize=10]; 0 13 2 4 5
 node [shape=circle,fixedsize=true,width=0.2,fontsize=10];
 s -> 0
 0 -> 13 [label="a",fontsize=10]
 0 -> 2 [label="b",fontsize=10]
 13 -> 13 [label="a",fontsize=10]
 2 -> 4 [label="a",fontsize=10]
 4 -> 4 [label="a",fontsize=10]
 2 -> 5 [label="b",fontsize=10]
 5 -> 5 [label="b",fontsize=10]
 fontsize=10

} </graph>

Input Analysis

In	Input	In+1 / Token
0	aababb$	13
13	ababb$	13
13	babb$	T1 (aa)
0	babb$	2
2	abb$	4
4	bb$	T2 (ba)
0	bb$	2
2	b$	5
5	$	T3 (bb)

The input string aababb is, after 9 steps, split into three tokens: T1 (corresponding to lexeme aa), T2 (ba), and T3 (bb).