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.
| NFA built by Thompson's algorithm
|
| b)*abb(a
|
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
|
-
|
-
|
-
|
| Graphical representation of the DFA
|
| b)*abb(a
|
| DFA minimization tree
|
| {{{2}}}
|
Input Analysis
| In
|
Input
|
In+1 / Token
|
| 0
|
aaabaaaaa$
|
1
|
| 1
|
aabaaaaa$
|
3
|
| 3
|
abaaaaa$
|
4
|
| 4
|
baaaaa$
|
error (backtracking)
|
| 3
|
abaaaaa$
|
T1 (aa)
|
| 0
|
abaaaaa$
|
1
|
| 1
|
baaaaa$
|
T3 (a)
|
| 0
|
baaaaa$
|
2
|
| 2
|
aaaaa$
|
T3 (b)
|
| 0
|
aaaaa$
|
1
|
| 1
|
aaaa$
|
3
|
| 3
|
aaa$
|
4
|
| 4
|
aa$
|
5
|
| 5
|
a$
|
T2 (aaaa)
|
| 0
|
a$
|
1
|
| 1
|
$
|
T3 (a)
|
The input string aaabaaaaa is, after 16 steps, split into three tokens: T1 (corresponding to lexeme aa), T3 (a), T3 (b), T2 (aaaa), and T3 (a).