Theoretical Aspects of Lexical Analysis/Exercise 7

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

NFA

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

HTTP-Response: 
error code: 1015


Diagram-Code:
digraph nfa {
     { node [shape=circle style=invis] s }
  rankdir=LR; ratio=0.5
  node [shape=doublecircle,fixedsize=true,width=0.2,fontsize=10]; 8 12 20
  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
  5 -> 8
  6 -> 7 [label="b",fontsize=10]
  7 -> 8

  0 -> 9
  9 -> 10
  9 -> 12
  10 -> 11 [label="a",fontsize=10]
  11 -> 10
  11 -> 12

  0 -> 13
  13 -> 14
  13 -> 18
  14 -> 15
  14 -> 17
  15 -> 16 [label="b",fontsize=10]
  16 -> 15
  16 -> 17
  17 -> 20
  18 -> 19 [label="a",fontsize=10]
  19 -> 20
  fontsize=10
}

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, 14, 15, 17, 18, 20	0 (T1)
0	a	4, 11, 19	3, 4, 5, 8, 10, 11, 12, 19, 20	1 (T1)
0	b	7, 16	7, 8, 15, 16, 17, 20	2 (T1)
1	a	4, 11	3, 4, 5, 8, 10, 11, 12	3 (T1)
1	b	-	-	-
2	a	-	-	-
2	b	16	15, 16, 17, 20	4 (T3)
3	a	4, 11	3, 4, 5, 8, 10, 11, 12	3 (T1)
3	b	-	-	-
4	a	-	-	-
4	b	16	15, 16, 17, 20	4 (T3)

Graphically, the DFA is represented as follows:

HTTP-Response: 
error code: 1015


Diagram-Code:
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
  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="b",fontsize=10]
  3 -> 3 [label="a",fontsize=10]
  4 -> 4 [label="b",fontsize=10]
  fontsize=10
}

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

HTTP-Response: 
error code: 1015


Diagram-Code:
digraph mintree { 
  node [shape=none,fixedsize=true,width=0.3,fontsize=10]
  "{0, 1, 2, 3, 4}" -> "{}" [label="NF",fontsize=10]
  "{0, 1, 2, 3, 4}" -> "{0, 1, 2, 3, 4} " [label="  F",fontsize=10]
  "{0, 1, 2, 3, 4} " -> "{0, 1, 2, 3}" [label="  T1",fontsize=10]
  "{0, 1, 2, 3, 4} " -> "{4}" [label="  T3",fontsize=10]
  "{0, 1, 2, 3}" -> "{0, 1, 3}" [label="  a",fontsize=10]
  "{0, 1, 2, 3}" -> "{2}" 
  "{0, 1, 3}" -> "{0}" [label="  b",fontsize=10]
  "{0, 1, 3}" -> "{1,3}" 
  "{1,3}" -> "{1,3} " [label="  a,b",fontsize=10]
  fontsize=10
}

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.

HTTP-Response: 
error code: 1015


Diagram-Code:
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
  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="b",fontsize=10]
  4 -> 4 [label="b",fontsize=10]
  fontsize=10
}

Input Analysis

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

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