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.
The following is the result of applying Thompson's algorithm.
NFA built by Thompson's algorithm |
---|
State 3 recognizes the first expression (token T1); state 8 recognizes token T2; and state 14 recognizes token T3.
|
Determination table for the above NFA |
---|
{ |
Graphical representation of the DFA |
---|
|
DFA minimization tree |
---|
Note that before considering transition behavior, states are split according to the token they recognize.
The tree expansion for sets {0, 4} and {1, 2} was only tested for "a" (sufficient). Given the minimization tree, the final minimal DFA is exactly the same as the original DFA (all leaf sets are singular). |
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).