(New page: __NOTOC__ Compute the non-deterministic finite automaton (NFA) by using Thompson's algorithm. Compute the minimal deterministic finite automaton (DFA).<br/>The alphabet is Σ = { a, b }. I...) |
(→DFA) |
||
Line 158: | Line 158: | ||
"{1, 2, 3, 5}" -> "{5}" [label=" T2",fontsize=10] | "{1, 2, 3, 5}" -> "{5}" [label=" T2",fontsize=10] | ||
"{1, 2, 3, 5}" -> "{1, 2}" [label=" T3",fontsize=10] | "{1, 2, 3, 5}" -> "{1, 2}" [label=" T3",fontsize=10] | ||
+ | "{0, 4}" -> "{0}" //[label=" T3",fontsize=10] | ||
+ | "{0, 4}" -> "{4}" [label=" a",fontsize=10] | ||
"{1, 2}" -> "{1}" //[label=" T3",fontsize=10] | "{1, 2}" -> "{1}" //[label=" T3",fontsize=10] | ||
"{1, 2}" -> "{2}" [label=" a",fontsize=10] | "{1, 2}" -> "{2}" [label=" a",fontsize=10] | ||
Line 165: | Line 167: | ||
</graph> | </graph> | ||
− | The tree expansion for | + | 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). | Given the minimization tree, the final minimal DFA is exactly the same as the original DFA (all leaf sets are singular). |
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 3 recognizes the first expression (token T1); state 8 recognizes token T2; and state 14 recognizes token T3.
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 | - | - | - |
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 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$ | |
$ | ||
$ | ||
$ | ||
$ | ||
$ | ||
$ | ||
$ | ||
$ |
//The input string aaabaaaaa is, after 9 steps, split into three tokens: T1 (corresponding to lexeme ab), T2 (a), and T2 (abb).