(→DFA) |
|||
Line 160: | Line 160: | ||
"{0, 1, 2, 4}" -> "{2, 4}" [label=" a",fontsize=10] | "{0, 1, 2, 4}" -> "{2, 4}" [label=" a",fontsize=10] | ||
fontsize=10 | fontsize=10 | ||
− | |||
} | } | ||
</dot-hack> | </dot-hack> |
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. State 8 recognizes the first expression (token T1); state 12 recognizes token T2; and state 20 recognizes token T3.
Determination table for the above NFA:
In | α∈Σ | move(In, α) | ε-closure(move(In, α)) | In+1 = ε-closure(move(In, α)) |
---|---|---|---|---|
- | - | 0 | 0, 1, 2, 4, 5, 7, 8, 9, 10, 12, 13, 14, 16, 17, 19, 20 | 0 (T1) |
0 | a | 3, 11, 18 | 3, 8, 10, 11, 12, 17, 18, 19, 20 | 1 (T1) |
0 | b | 6, 15 | 5, 6, 7, 8, 15, 20 | 2 (T1) |
1 | a | 11, 18 | 10, 11, 12, 17, 18, 19, 20 | 3 (T2) |
1 | b | - | - | - |
2 | a | - | - | - |
2 | b | 6 | 5, 6, 7, 8 | 4 (T1) |
3 | a | 11, 18 | 10, 11, 12, 17, 18, 19, 20 | 3 (T2) |
3 | b | - | - | - |
4 | a | - | - | - |
4 | b | 6 | 5, 6, 7, 8 | 4 (T1) |
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 (transitions for super-state {2,4}).
Given the minimization tree, the final minimal DFA is as follows. Note that states 1 and 3 cannot be the same since they recognize different tokens.
In | Input | In+1 / Token |
---|---|---|
0 | aababb$ | 1 |
1 | ababb$ | 3 |
3 | babb$ | T2 (aa) |
0 | babb$ | 24 |
24 | abb$ | T1 (b) |
0 | abb$ | 1 |
1 | bb$ | T1 (a) |
0 | bb$ | 24 |
24 | b$ | 24 |
24 | $ | T1 (bb) |
The input string aababb is, after 10 steps, split into three tokens: T2 (corresponding to lexeme aa), T1 (b), T1 (a), and T1 (bb).