Use Thompson's algorithm to build the NFA for the following regular expression. Build the corresponding DFA and minimize it.
- ((ε|a)b)*
(3 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> | |
− | The | + | <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 { | digraph nfa { | ||
{ node [shape=circle style=invis] start } | { node [shape=circle style=invis] start } | ||
Line 23: | Line 32: | ||
7 -> 1; 7 -> 8 | 7 -> 1; 7 -> 8 | ||
fontsize=10 | fontsize=10 | ||
− | |||
} | } | ||
− | </ | + | </dot-hack> |
− | |||
− | |||
− | |||
− | |||
+ | Applying the determination algorithm to the above NFA, the following determination table is obtained: | ||
{| cellspacing="2" | {| cellspacing="2" | ||
! style="padding-left: 20px; padding-right: 20px; background: wheat;" | I<sub>n</sub> | ! style="padding-left: 20px; padding-right: 20px; background: wheat;" | I<sub>n</sub> | ||
Line 84: | Line 89: | ||
! style="text-align: left; font-weight:normal; vertical-align: top; width: 50%;" |Graphically, the DFA is represented as follows: | ! style="text-align: left; font-weight:normal; vertical-align: top; width: 50%;" |Graphically, the DFA is represented as follows: | ||
− | < | + | <dot-hack> |
digraph dfa { | digraph dfa { | ||
{ node [shape=circle style=invis] start } | { node [shape=circle style=invis] start } | ||
Line 97: | Line 102: | ||
2 -> 2 [label="b"] | 2 -> 2 [label="b"] | ||
fontsize=10 | fontsize=10 | ||
− | |||
} | } | ||
− | </ | + | </dot-hack> |
Given the minimization tree to the right, the final minimal DFA is: | Given the minimization tree to the right, the final minimal DFA is: | ||
− | < | + | <dot-hack> |
digraph dfamin { | digraph dfamin { | ||
{ node [shape=circle style=invis] start } | { node [shape=circle style=invis] start } | ||
Line 113: | Line 117: | ||
1 -> 02 [label="b"] | 1 -> 02 [label="b"] | ||
fontsize=10 | fontsize=10 | ||
− | |||
} | } | ||
− | </ | + | </dot-hack> |
− | ! style="text-align: left; font-weight:normal; vertical-align: top; width: 50%;" | The minimization tree is as follows | + | ! style="text-align: left; font-weight:normal; vertical-align: top; width: 50%;" | The minimization tree is as follows. |
− | < | + | <dot-hack> |
digraph mintree { | digraph mintree { | ||
node [shape=none,fixedsize=true,width=0.2,fontsize=10] | node [shape=none,fixedsize=true,width=0.2,fontsize=10] | ||
Line 126: | Line 129: | ||
"{0, 2}" -> "{0,2} " [label=" a,b",fontsize=10] | "{0, 2}" -> "{0,2} " [label=" a,b",fontsize=10] | ||
fontsize=10 | fontsize=10 | ||
− | |||
} | } | ||
− | </ | + | </dot-hack> |
|} | |} | ||
+ | <!-- ====================== END OF SOLUTION ====================== --> | ||
+ | </div> | ||
+ | </div> | ||
+ | </div> | ||
+ | |||
+ | [[category:Compiladores]] | ||
+ | [[category:Ensino]] | ||
− | |||
− | |||
[[en:Theoretical Aspects of Lexical Analysis]] | [[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, 4, 6, 8 | 0 |
0 | a | 5 | 5, 6 | 1 |
0 | b | 7 | 1, 2, 3, 4, 6, 7, 8 | 2 |
1 | a | - | - | - |
1 | b | 7 | 1, 2, 3, 4, 6, 7, 8 | 2 |
2 | a | 5 | 5, 6 | 1 |
2 | b | 7 | 1, 2, 3, 4, 6, 7, 8 | 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. |
---|