Theoretical Aspects of Lexical Analysis/Exercise 15

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

• G = { a*|c, a|b*, bc* }, input string = aaabcacc

NFA

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

<dot-hack> digraph nfa {

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

 s -> 0

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

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

 0 -> 17 
 17 -> 18 [label="b",fontsize=10]
 18 -> 19
 18 -> 21
 19 -> 20 [label="c",fontsize=10]
 20 -> 19
 20 -> 21

 fontsize=10

} </dot-hack>

DFA

Determination table for the above NFA:

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

Graphically, the DFA is represented as follows:

<dot-hack> 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 6
 node [shape=circle,fixedsize=true,width=0.2,fontsize=10];
 s -> 0
 0 -> 1 [label="a",fontsize=10]
 0 -> 2 [label="b",fontsize=10]
 0 -> 3 [label="c",fontsize=10]
 1 -> 4 [label="a",fontsize=10]
 2 -> 5 [label="b",fontsize=10]
 2 -> 6 [label="c",fontsize=10]
 4 -> 4 [label="a",fontsize=10]
 5 -> 5 [label="b",fontsize=10]
 6 -> 6 [label="c",fontsize=10]
 fontsize=10

} </dot-hack>

The minimization tree is as follows. Note that before considering transition behavior, states are split according to the token they recognize.

<dot-hack> digraph mintree {

 node [shape=none,fixedsize=true,width=0.3,fontsize=10]
 "{0, 1, 2, 3, 4, 5, 6}" -> "{}       " [label="NF",fontsize=10]
 "{0, 1, 2, 3, 4, 5, 6}" -> "{0, 1, 2, 3, 4, 5, 6} " [label="  F",fontsize=10]
 "{0, 1, 2, 3, 4, 5, 6} " -> "{0, 1, 3, 4}" [label="  T1",fontsize=10]
 "{0, 1, 2, 3, 4, 5, 6} " -> "{2, 5}" [label="  T2",fontsize=10]
 "{0, 1, 2, 3, 4, 5, 6} " -> "{6}" [label="  T3",fontsize=10]
 "{0, 1, 3, 4}" -> "{0, 1, 4}" [label="  a",fontsize=10]
 "{0, 1, 3, 4}" -> "{3}"
 "{2, 5}" -> "{2}" [label="  c",fontsize=10]
 "{2, 5}" -> "{5}" 
 "{0, 1, 4}" -> "{0}" [label="  b",fontsize=10]
 "{0, 1, 4}" -> "{1, 4}" 
 "{1, 4}" -> "{1, 4} " [label="  a, b, c",fontsize=10]
 fontsize=10

} </dot-hack>

Given the minimization tree, the final minimal DFA is as follows.

<dot-hack> digraph dfa {

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

} </dot-hack>

Input Analysis

In	Input	In+1 / Token
0	aaabcacc$	14
14	aabcacc$	14
14	abcacc$	14
14	bcacc$	T1 (aaa)
0	bcacc$	2
2	cacc$	6
6	acc$	T3 (bc)
0	acc$	14
14	cc$	T1 (a)
0	cc$	3
3	c$	T1 (c)
0	c$	3
3	$	T1 (c)

The input string aaabcacc is, after 13 steps, split into five tokens: T1 (corresponding to lexeme aaa), T3 (bc), T1 (a), T1 (c), T1 (c).