(→Minimal DFA) |
(→Minimal DFA) |
||
| Line 205: | Line 205: | ||
</graph> | </graph> | ||
| − | == Minimal DFA == | + | == Minimal DFA == |
| − | The minimization tree is as follows. | + | The minimization tree is as follows. |
<graph> | <graph> | ||
| Line 221: | Line 221: | ||
//label="Minimization tree" | //label="Minimization tree" | ||
} | } | ||
| − | </graph> | + | </graph> |
| − | 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 | + | 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 both "a" or "b" transitions (remember that, at this stage, we assume that individual states -- i.e., the final states -- are all indistinguishable). |
| − | Given the minimization tree above, the final minimal DFA is: | + | Given the minimization tree above, the final minimal DFA is: <graph> |
| − | <graph> | ||
digraph dfamin { | digraph dfamin { | ||
{ node [shape=circle style=invis] s } | { node [shape=circle style=invis] s } | ||
| Line 244: | Line 243: | ||
//label="DFA for (a|b)*abb(a|b)*" | //label="DFA for (a|b)*abb(a|b)*" | ||
} | } | ||
| − | </graph> | + | </graph> |
| − | [[ | + | [[Category:Teaching]] [[Category:Compilers]] [[en:Theoretical Aspects of Lexical Analysis|en:Theoretical Aspects of Lexical Analysis]] |
| − | [[ | ||
| − | [[en:Theoretical Aspects of Lexical Analysis]] | ||
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 both "a" or "b" transitions (remember that, at this stage, we assume that individual states -- i.e., the final states -- are all indistinguishable).
Given the minimization tree above, the final minimal DFA is: