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 = { ab, ab*, a|b }, input string = abaabb
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.
Applying the determination algorithm to the above NFA, the following determination table is obtained:
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, 6, 8, 11, 14
|
1 (T2)
|
0
|
b
|
13
|
13, 14
|
2 (T3)
|
1
|
a
|
-
|
-
|
-
|
1
|
b
|
3, 7
|
3, 6, 7, 8
|
3 (T1)
|
2
|
a
|
-
|
-
|
-
|
2
|
b
|
-
|
-
|
-
|
3
|
a
|
-
|
-
|
-
|
3
|
b
|
7
|
6, 7, 8
|
4 (T2)
|
4
|
a
|
-
|
-
|
-
|
4
|
b
|
7
|
6, 7, 8
|
4 (T2)
|
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.
The tree expansion for non-splitting sets has been omitted for simplicity ("a" transition for final states {1, 4}).
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
|
abaabb$
|
1
|
1
|
baabb$
|
3
|
3
|
aabb$
|
T1
|
0
|
aabb$
|
1
|
1
|
abb$
|
T2
|
0
|
abb$
|
1
|
1
|
bb$
|
3
|
3
|
b$
|
4
|
4
|
$
|
T2
|
The input string abaabb is, after 9 steps, split into three tokens: T1 (corresponding to lexeme ab), T2 (a), and T2 (abb).