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
|
|
{
|
| 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).