Theoretical Aspects of Lexical Analysis/Exercise 6

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 = { aa, aaaa, a|b}, input string = aaabaaaaa

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="a",fontsize=10]

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

 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, 11, 14	1 (T3)
0	b	13	13, 14	2 (T3)
1	a	3, 6	3, 6	3 (T1)
1	b	-	-	-
2	a	-	-	-
2	b	-	-	-
3	a	7	7	4
3	b	-	-	-
4	a	8	8	5 (T2)
4	b	-	-	-
5	a	-	-	-
5	b	-	-	-

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 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]
 3 -> 4 [label="a",fontsize=10]
 4 -> 5 [label="a",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, 5}" -> "{0, 4}" [label=" NF",fontsize=10]
 "{0, 1, 2, 3, 4, 5}" -> "{1, 2, 3, 5}" [label="  F",fontsize=10]
 "{1, 2, 3, 5}" -> "{3}" [label="  T1",fontsize=10]
 "{1, 2, 3, 5}" -> "{5}" [label="  T2",fontsize=10]
 "{1, 2, 3, 5}" -> "{1, 2}" [label="  T3",fontsize=10]
 "{0, 4}" -> "{0}" //[label="  T3",fontsize=10]
 "{0, 4}" -> "{4}" [label="  a",fontsize=10]
 "{1, 2}" -> "{1}" //[label="  T3",fontsize=10]
 "{1, 2}" -> "{2}" [label="  a",fontsize=10]
 fontsize=10
 //label="Minimization tree"

} </graph>

The tree expansion for sets {0, 4} and {1, 2} was only tested for "a" (sufficient).

Given the minimization tree, the final minimal DFA is exactly the same as the original DFA (all leaf sets are singular).

Input Analysis

In	Input	In+1 / Token
0	aaabaaaaa$
	$
	$
	$
	$
	$
	$
	$
	$