(New page: Use Thompson's algorithm to build the NFA for the following regular expression. Build the corresponding DFA and minimize it. * <nowiki>(a|b)*abb(a|b)*</nowiki> == Solution == [[category...) |
|||
Line 3: | Line 3: | ||
== Solution == | == Solution == | ||
+ | |||
+ | === NFA === | ||
+ | |||
+ | The following is the result of applying Thompson's algorithm. | ||
+ | |||
+ | <graph> | ||
+ | digraph nfa { | ||
+ | { node [shape=circle style=invis] start } | ||
+ | rankdir=LR; ratio=0.5 | ||
+ | node [shape=doublecircle,fixedsize=true,width=0.2,fontsize=10]; 17 | ||
+ | node [shape=circle,fixedsize=true,width=0.2,fontsize=10]; | ||
+ | |||
+ | start -> 0 | ||
+ | 0 -> 1 | ||
+ | 1 -> 2 | ||
+ | 1 -> 4 | ||
+ | 2 -> 3 [label="a",fontsize=10] | ||
+ | 4 -> 5 [label="b",fontsize=10] | ||
+ | 3 -> 6 | ||
+ | 5 -> 6 | ||
+ | 6 -> 1 | ||
+ | 6 -> 7 | ||
+ | 0 -> 7 | ||
+ | |||
+ | 7 -> 8 [label="a",fontsize=10] | ||
+ | 8 -> 9 [label="b",fontsize=10] | ||
+ | 9 -> 10 [label="b",fontsize=10] | ||
+ | |||
+ | 10 -> 11 | ||
+ | 11 -> 12 | ||
+ | 11 -> 14 | ||
+ | 12 -> 13 [label="a",fontsize=10] | ||
+ | 14 -> 15 [label="b",fontsize=10] | ||
+ | 13 -> 16 | ||
+ | 15 -> 16 | ||
+ | 16 -> 11 | ||
+ | 16 -> 17 | ||
+ | 10 -> 17 | ||
+ | |||
+ | |||
+ | fontsize=10 | ||
+ | //label="NFA for (a|b)*abb(a|b)*" | ||
+ | } | ||
+ | </graph> | ||
+ | |||
+ | === DFA === | ||
+ | |||
+ | Determination table for the above NFA: | ||
+ | |||
+ | {| cellspacing="2" | ||
+ | ! style="padding-left: 20px; padding-right: 20px; background: wheat;" | I<sub>n</sub> | ||
+ | ! style="padding-left: 20px; padding-right: 20px; background: wheat;" | α∈Σ | ||
+ | ! style="padding-left: 20px; padding-right: 20px; background: wheat;" | move(I<sub>n</sub>, α) | ||
+ | ! style="padding-left: 20px; padding-right: 20px; background: wheat;" | ε-closure(move(I<sub>n</sub>, α)) | ||
+ | ! style="padding-left: 20px; padding-right: 20px; background: wheat;" | I<sub>n+1</sub> = ε-closure(move(I<sub>n</sub>, α)) | ||
+ | |- | ||
+ | ! style="font-weight: normal; align: center; background: #ffffcc;" | - | ||
+ | ! style="font-weight: normal; align: center; background: #ffffcc;" | - | ||
+ | ! style="font-weight: normal; align: center; background: #ffffcc;" | 0 | ||
+ | ! style="font-weight: normal; align: left; background: #ffffcc;" | 0, 1, 2, 4, 7 | ||
+ | ! style="font-weight: normal; align: center; background: #ffffcc;" | 0 | ||
+ | |- | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 0 | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | a | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 3, 8 | ||
+ | ! style="font-weight: normal; align: left; background: #e6e6e6;" | 1, 2, 3, 4, 6, 7, 8 | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 1 | ||
+ | |- | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 0 | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | b | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 5 | ||
+ | ! style="font-weight: normal; align: left; background: #e6e6e6;" | 1, 2, 4, 5, 6, 7 | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 2 | ||
+ | |- | ||
+ | ! style="font-weight: normal; align: center; background: #ffffcc;" | 1 | ||
+ | ! style="font-weight: normal; align: center; background: #ffffcc;" | a | ||
+ | ! style="font-weight: normal; align: center; background: #ffffcc;" | 3, 8 | ||
+ | ! style="font-weight: normal; align: left; background: #ffffcc;" | 1, 2, 3, 4, 6, 7, 8 | ||
+ | ! style="font-weight: normal; align: center; background: #ffffcc;" | 1 | ||
+ | |- | ||
+ | ! style="font-weight: normal; align: center; background: #ffffcc;" | 1 | ||
+ | ! style="font-weight: normal; align: center; background: #ffffcc;" | b | ||
+ | ! style="font-weight: normal; align: center; background: #ffffcc;" | 5, 9 | ||
+ | ! style="font-weight: normal; align: left; background: #ffffcc;" | 1, 2, 4, 5, 6, 7, 9 | ||
+ | ! style="font-weight: normal; align: center; background: #ffffcc;" | 3 | ||
+ | |- | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 2 | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | a | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 3, 8 | ||
+ | ! style="font-weight: normal; align: left; background: #e6e6e6;" | 1, 2, 3, 4, 6, 7, 8 | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 1 | ||
+ | |- | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 2 | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | b | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 5 | ||
+ | ! style="font-weight: normal; align: left; background: #e6e6e6;" | 1, 2, 4, 5, 6, 7 | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 2 | ||
+ | |- | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 3 | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | a | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 3, 8 | ||
+ | ! style="font-weight: normal; align: left; background: #e6e6e6;" | 1, 2, 3, 4, 6, 7, 8 | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 1 | ||
+ | |- | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 3 | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | b | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 5, 10 | ||
+ | ! style="font-weight: normal; align: left; background: #e6e6e6;" | 1, 2, 4, 5, 6, 7, 10, 11, 12, 14, '''17''' | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | '''4''' | ||
+ | |- | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 4 | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | a | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 3, 8, 13 | ||
+ | ! style="font-weight: normal; align: left; background: #e6e6e6;" | 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16, '''17''' | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | '''5''' | ||
+ | |- | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 4 | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | b | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 5, 15 | ||
+ | ! style="font-weight: normal; align: left; background: #e6e6e6;" | 1, 2, 4, 5, 6, 7, 11, 12, 14, 15, 16, '''17''' | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | '''6''' | ||
+ | |- | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 5 | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | a | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 3, 8, 13 | ||
+ | ! style="font-weight: normal; align: left; background: #e6e6e6;" | 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16, '''17''' | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | '''5''' | ||
+ | |- | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 5 | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | b | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 5, 15 | ||
+ | ! style="font-weight: normal; align: left; background: #e6e6e6;" | 1, 2, 4, 5, 6, 7, 11, 12, 14, 15, 16, '''17''' | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | '''6''' | ||
+ | |- | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 6 | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | a | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 3, 8, 13 | ||
+ | ! style="font-weight: normal; align: left; background: #e6e6e6;" | 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16, '''17''' | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | '''5''' | ||
+ | |- | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 6 | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | b | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 5, 15 | ||
+ | ! style="font-weight: normal; align: left; background: #e6e6e6;" | 1, 2, 4, 5, 6, 7, 11, 12, 14, 15, 16, '''17''' | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | '''6''' | ||
+ | |} | ||
+ | |||
+ | |||
+ | {| width="100%" | ||
+ | ! style="text-align: left; font-weight:normal; vertical-align: top; width: 50%;" |Graphically, the DFA is represented as follows: | ||
+ | |||
+ | <graph> | ||
+ | digraph dfa { | ||
+ | { node [shape=circle style=invis] start } | ||
+ | rankdir=LR; ratio=0.5 | ||
+ | node [shape=doublecircle,fixedsize=true,width=0.2,fontsize=10]; 4 5 6 | ||
+ | node [shape=circle,fixedsize=true,width=0.2,fontsize=10]; | ||
+ | start -> 0 | ||
+ | 0 -> 1 [label="a"] | ||
+ | 0 -> 2 [label="b"] | ||
+ | 1 -> 1 [label="a"] | ||
+ | 1 -> 3 [label="b"] | ||
+ | 2 -> 1 [label="a"] | ||
+ | 2 -> 2 [label="b"] | ||
+ | 3 -> 1 [label="a"] | ||
+ | 3 -> 4 [label="b"] | ||
+ | 4 -> 5 [label="a"] | ||
+ | 4 -> 6 [label="b"] | ||
+ | 5 -> 5 [label="a"] | ||
+ | 5 -> 6 [label="b"] | ||
+ | 6 -> 5 [label="a"] | ||
+ | 6 -> 6 [label="b"] | ||
+ | fontsize=10 | ||
+ | //label="DFA for (a|b)*abb(a|b)*" | ||
+ | } | ||
+ | </graph> | ||
+ | |||
+ | Given the minimization tree to the right, the final minimal DFA is: | ||
+ | <graph> | ||
+ | digraph dfamin { | ||
+ | { node [shape=circle style=invis] start } | ||
+ | rankdir=LR; ratio=0.5 | ||
+ | node [shape=doublecircle,fixedsize=true,width=0.4,fontsize=10]; 456 | ||
+ | node [shape=circle,fixedsize=true,width=0.2,fontsize=10]; | ||
+ | start -> 02 | ||
+ | 02 -> 1 [label="a"] | ||
+ | 02 -> 02 [label="b"] | ||
+ | 1 -> 1 [label="a"] | ||
+ | 1 -> 3 [label="b"] | ||
+ | 3 -> 1 [label="a"] | ||
+ | 3 -> 456 [label="b"] | ||
+ | 456 -> 456 [label="a"] | ||
+ | 456 -> 456 [label="b"] | ||
+ | fontsize=10 | ||
+ | //label="DFA for (a|b)*abb(a|b)*" | ||
+ | } | ||
+ | </graph> | ||
+ | |||
+ | ! style="text-align: left; font-weight:normal; vertical-align: top; width: 50%;" | The minimization tree is as follows. As can be seen, the states are indistinguishable. | ||
+ | |||
+ | <graph> | ||
+ | digraph mintree { | ||
+ | node [shape=none,fixedsize=true,width=0.3,fontsize=10] | ||
+ | "{0, 1, 2, 3, 4, 5, 6}" -> "{0, 1, 2, 3}" [label="NF",fontsize=10] | ||
+ | "{0, 1, 2, 3, 4, 5, 6}" -> "{4, 5, 6}" [label=" F",fontsize=10] | ||
+ | //"{0, 1, 2, 3}" -> "{0, 1, 2, 3} " [label=" a",fontsize=10] | ||
+ | "{0, 1, 2, 3}" -> "{0, 1, 2}" | ||
+ | "{0, 1, 2, 3}" -> "{3} " [label=" b",fontsize=10] | ||
+ | "{0, 1, 2}" -> "{0, 2} " | ||
+ | "{0, 1, 2}" -> "{1} " [label=" b",fontsize=10] | ||
+ | fontsize=10 | ||
+ | //label="Minimization tree" | ||
+ | } | ||
+ | </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 either "a" or "b" transitions. | ||
+ | |} | ||
[[category:Teaching]] | [[category:Teaching]] | ||
[[category:Compilers]] | [[category:Compilers]] | ||
[[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, 15 | 1, 2, 4, 5, 6, 7, 11, 12, 14, 15, 16, 17 | 6 |
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 |
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.
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. |
---|