(→DFA) |
|||
| Line 129: | Line 129: | ||
node [shape=none,fixedsize=true,width=0.2,fontsize=10] | node [shape=none,fixedsize=true,width=0.2,fontsize=10] | ||
" {0, 1, 2}" -> "{}" [label="NF",fontsize=10] | " {0, 1, 2}" -> "{}" [label="NF",fontsize=10] | ||
| − | " {0, 1, 2}" -> "{0, 1, 2}" [label="F",fontsize=10] | + | " {0, 1, 2}" -> "{0, 1, 2}" [label=" F",fontsize=10] |
| − | "{0, 1, 2}" -> "{0, 1, 2} " [label="a,b",fontsize=10] | + | "{0, 1, 2}" -> "{0, 1, 2} " [label=" a,b",fontsize=10] |
fontsize=10 | fontsize=10 | ||
//label="Minimization tree" | //label="Minimization tree" | ||
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, 3, 5, 6, 7, 9, 10, 11 | 0 |
| 0 | a | 4 | 1, 2, 3, 4, 5, 6, 7, 9, 10, 11 | 1 |
| 0 | b | 8 | 1, 2, 3, 5, 6, 7, 8, 9, 10, 11 | 2 |
| 1 | a | 4 | 1, 2, 3, 4, 5, 6, 7, 9, 10, 11 | 1 |
| 1 | b | 8 | 1, 2, 3, 5, 6, 7, 8, 9, 10, 11 | 2 |
| 2 | a | 4 | 1, 2, 3, 4, 5, 6, 7, 9, 10, 11 | 1 |
| 2 | b | 8 | 1, 2, 3, 5, 6, 7, 8, 9, 10, 11 | 2 |
| Graphically, the DFA is represented as follows:
Given the minimization tree to the right, the final minimal DFA is:
|
The minimization tree is as follows. As can be seen, the states are indistinguishable.
|
|---|