(→Minimal DFA) |
(→Minimal DFA) |
||
| Line 238: | Line 238: | ||
1 -> 3 [label="b",fontsize=10] | 1 -> 3 [label="b",fontsize=10] | ||
3 -> 1 [label="a",fontsize=10] | 3 -> 1 [label="a",fontsize=10] | ||
| − | 3 -> | + | 3 -> 45678 [label="b",fontsize=10] |
45678 -> 45678 [label="a",fontsize=10] | 45678 -> 45678 [label="a",fontsize=10] | ||
45678 -> 45678 [label="b",fontsize=10] | 45678 -> 45678 [label="b",fontsize=10] | ||
Use Thompson's algorithm to build the NFA for the following regular expression. Build the corresponding DFA and minimize it.
The following is the result of applying Thompson's algorithm.
Determination table for the above NFA:
| In | α∈Σ | move(In, α) | ε-closure(move(In, α)) | In+1 = ε-closure(move(In, α)) |
|---|---|---|---|---|
| - | - | 0 | 0, 1, 2, 4, 7 | 0 |
| 0 | a | 3, 8 | 1, 2, 3, 4, 6, 7, 8 | 1 |
| 0 | b | 5 | 1, 2, 4, 5, 6, 7 | 2 |
| 1 | a | 3, 8 | 1, 2, 3, 4, 6, 7, 8 | 1 |
| 1 | b | 5, 9 | 1, 2, 4, 5, 6, 7, 9 | 3 |
| 2 | a | 3, 8 | 1, 2, 3, 4, 6, 7, 8 | 1 |
| 2 | b | 5 | 1, 2, 4, 5, 6, 7 | 2 |
| 3 | a | 3, 8 | 1, 2, 3, 4, 6, 7, 8 | 1 |
| 3 | b | 5, 10 | 1, 2, 4, 5, 6, 7, 10, 11, 12, 14, 17 | 4 |
| 4 | a | 3, 8, 13 | 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16, 17 | 5 |
| 4 | b | 5, 15 | 1, 2, 4, 5, 6, 7, 11, 12, 14, 15, 16, 17 | 6 |
| 5 | a | 3, 8, 13 | 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16, 17 | 5 |
| 5 | b | 5, 9, 15 | 1, 2, 4, 5, 6, 7, 9, 11, 12, 14, 15, 16, 17 | 7 |
| 6 | a | 3, 8, 13 | 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16, 17 | 5 |
| 6 | b | 5, 15 | 1, 2, 4, 5, 6, 7, 11, 12, 14, 15, 16, 17 | 6 |
| 7 | a | 3, 8, 13 | 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16, 17 | 5 |
| 7 | b | 5, 10, 15 | 1, 2, 4, 5, 6, 7, 10, 11, 12, 14, 15, 16, 17 | 8 |
| 8 | a | 3, 8, 13 | 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16, 17 | 5 |
| 8 | b | 5, 15 | 1, 2, 4, 5, 6, 7, 11, 12, 14, 15, 16, 17 | 6 |
Graphically, the DFA is represented as follows:
The minimization tree is as follows.
The tree expansion for non-splitting sets has been omitted for simplicity ("a" transition for non-final states and the {0, 2} "a" and "b" transitions. The final states are all indistinguishable, regarding either "a" or "b" transitions.
Given the minimization tree above, the final minimal DFA is: