Theoretical Aspects of Lexical Analysis/Exercise 18

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 = { ab*, (a|c)*, bc*}, input string = abbcac

NFA

The following is the result of applying Thompson's algorithm.

State 5 recognizes the first expression (token T1); state 13 recognizes token T2; and state 18 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]; 5 13 18
 node [shape=circle,fixedsize=true,width=0.2,fontsize=10];

 s -> 0

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

 0 -> 6
 6 -> 7
 6 -> 13
 7 -> 8
 7 -> 10
 8 -> 9 [label="a",fontsize=10]
 9 -> 12
 10 -> 11 [label="c",fontsize=10]
 11 -> 12
 12 -> 7
 12 -> 13

 0 -> 14
 14 -> 15 [label="b",fontsize=10]
 15 -> 16
 15 -> 18
 16 -> 17 [label="c",fontsize=10]
 17 -> 16
 17 -> 18
 fontsize=10

} </graph>

DFA

Determination table for the above NFA:

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

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