Use Thompson's algorithm to build the NFA for the following regular expression. Build the corresponding DFA and minimize it.
- (a*|b*)*
(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*)*</nowiki>) |
|||
(7 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
+ | __NOTOC__ | ||
+ | <div class="section-container auto" data-section> | ||
+ | <div class="section"> | ||
+ | <p class="title" data-section-title>Problem</p> | ||
+ | <div class="content" data-section-content> | ||
+ | <!-- ====================== START OF PROBLEM ====================== --> | ||
Use Thompson's algorithm to build the NFA for the following regular expression. Build the corresponding DFA and minimize it. | Use Thompson's algorithm to build the NFA for the following regular expression. Build the corresponding DFA and minimize it. | ||
− | * <nowiki>(a*|b*)*</nowiki> | + | * '''<nowiki>(a*|b*)*</nowiki>''' |
+ | <!-- ====================== END OF PROBLEM ====================== --> | ||
+ | </div> | ||
+ | </div> | ||
+ | <div class="section"> | ||
+ | <p class="title" data-section-title>Solution</p> | ||
+ | <div class="content" data-section-content> | ||
+ | <!-- ====================== START OF SOLUTION ====================== --> | ||
+ | The non-deterministic finite automaton (NFA), built by applying Thompson's algorithm to the regular expression '''<nowiki>(a*|b*)*</nowiki>''' is the following: | ||
+ | <dot-hack> | ||
+ | digraph nfa { | ||
+ | { node [shape=circle style=invis] start } | ||
+ | rankdir=LR; ratio=0.5 | ||
+ | node [shape=doublecircle,fixedsize=true,width=0.2,fontsize=10]; 11 | ||
+ | node [shape=circle,fixedsize=true,width=0.2,fontsize=10]; | ||
+ | start -> 0 | ||
+ | 0 -> 1; 0 -> 11 | ||
+ | 1 -> 2; 1 -> 6 | ||
+ | 2 -> 3; 2 -> 5 | ||
+ | 3 -> 4 [label="a",fontsize=10] | ||
+ | 4 -> 3; 4 -> 5 | ||
+ | 5 -> 10 | ||
+ | 6 -> 7; 6 -> 9 | ||
+ | 7 -> 8 [label="b",fontsize=10] | ||
+ | 8 -> 7; 8 -> 9 | ||
+ | 9 -> 10 | ||
+ | 10 -> 1; 10 -> 11 | ||
+ | fontsize=10 | ||
+ | } | ||
+ | </dot-hack> | ||
+ | |||
+ | Applying the determination algorithm to the above NFA, the following determination table is obtained: | ||
+ | {| 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, 3, 5, 6, 7, 9, 10, '''11''' | ||
+ | ! 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;" | 4 | ||
+ | ! style="font-weight: normal; align: left; background: #e6e6e6;" | 1, 2, 3, 4, 5, 6, 7, 9, 10, '''11''' | ||
+ | ! 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;" | 8 | ||
+ | ! style="font-weight: normal; align: left; background: #e6e6e6;" | 1, 2, 3, 5, 6, 7, 8, 9, 10, '''11''' | ||
+ | ! 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;" | 4 | ||
+ | ! style="font-weight: normal; align: left; background: #ffffcc;" | 1, 2, 3, 4, 5, 6, 7, 9, 10, '''11''' | ||
+ | ! 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;" | 8 | ||
+ | ! style="font-weight: normal; align: left; background: #ffffcc;" | 1, 2, 3, 5, 6, 7, 8, 9, 10, '''11''' | ||
+ | ! style="font-weight: normal; align: center; background: #ffffcc;" | '''2''' | ||
+ | |- | ||
+ | ! 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;" | 4 | ||
+ | ! style="font-weight: normal; align: left; background: #e6e6e6;" | 1, 2, 3, 4, 5, 6, 7, 9, 10, '''11''' | ||
+ | ! 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;" | 8 | ||
+ | ! style="font-weight: normal; align: left; background: #e6e6e6;" | 1, 2, 3, 5, 6, 7, 8, 9, 10, '''11''' | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | '''2''' | ||
+ | |} | ||
+ | |||
+ | {| width="100%" | ||
+ | ! style="text-align: left; font-weight:normal; vertical-align: top; width: 50%;" |Graphically, the DFA is represented as follows: | ||
+ | <dot-hack> | ||
+ | digraph dfa { | ||
+ | { node [shape=circle style=invis] start } | ||
+ | rankdir=LR; ratio=0.5 | ||
+ | node [shape=doublecircle,fixedsize=true,width=0.2,fontsize=10]; 0 1 2 | ||
+ | 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 -> 2 [label="b"] | ||
+ | 2 -> 1 [label="a"] | ||
+ | 2 -> 2 [label="b"] | ||
+ | fontsize=10 | ||
+ | } | ||
+ | </dot-hack> | ||
+ | |||
+ | Given the minimization tree to the right, the final minimal DFA is: | ||
+ | <dot-hack> | ||
+ | digraph dfamin { | ||
+ | { node [shape=circle style=invis] start } | ||
+ | rankdir=LR; ratio=0.5 | ||
+ | node [shape=doublecircle,fixedsize=true,width=0.4,fontsize=10]; 012 | ||
+ | node [shape=circle,fixedsize=true,width=0.2,fontsize=10]; | ||
+ | start -> 012 | ||
+ | 012 -> 012 [label="a"] | ||
+ | 012 -> 012 [label="b"] | ||
+ | fontsize=10 | ||
+ | } | ||
+ | </dot-hack> | ||
+ | |||
+ | ! 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. | ||
+ | |||
+ | <dot-hack> | ||
+ | digraph mintree { | ||
+ | node [shape=none,fixedsize=true,width=0.2,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=" a,b",fontsize=10] | ||
+ | fontsize=10 | ||
+ | } | ||
+ | </dot-hack> | ||
+ | |} | ||
+ | <!-- ====================== END OF SOLUTION ====================== --> | ||
+ | </div> | ||
+ | </div> | ||
+ | </div> | ||
+ | |||
+ | [[category:Compiladores]] | ||
+ | [[category:Ensino]] | ||
+ | |||
+ | [[en:Theoretical Aspects of Lexical Analysis]] |
Problem
Use Thompson's algorithm to build the NFA for the following regular expression. Build the corresponding DFA and minimize it.
Solution
The non-deterministic finite automaton (NFA), built by applying Thompson's algorithm to the regular expression (a*|b*)* is the following:
Applying the determination algorithm to the above NFA, the following determination table is obtained:
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. |
---|