Line 1: | Line 1: | ||
− | + | {{TOCright}} | |
− | + | ||
− | + | ==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)*abb(a|b)*</nowiki>''' | * '''<nowiki>(a|b)*abb(a|b)*</nowiki>''' | ||
− | + | ||
− | + | == Solution == | |
− | + | ||
− | |||
− | |||
− | |||
− | |||
The non-deterministic finite automaton (NFA), built by applying Thompson's algorithm to the regular expression '''<nowiki>(a|b)*abb(a|b)*</nowiki>''' is the following: | The non-deterministic finite automaton (NFA), built by applying Thompson's algorithm to the regular expression '''<nowiki>(a|b)*abb(a|b)*</nowiki>''' is the following: | ||
+ | {{CollapsedCode|NFA| | ||
<graph> | <graph> | ||
digraph nfa { | digraph nfa { | ||
Line 54: | Line 48: | ||
} | } | ||
</graph> | </graph> | ||
+ | }} | ||
Applying the determination algorithm to the above NFA, the following determination table is obtained: | Applying the determination algorithm to the above NFA, the following determination table is obtained: | ||
+ | {{CollapsedCode|Determination table| | ||
{| 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 178: | Line 174: | ||
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''6''' | ! style="font-weight: normal; align: center; background: #e6e6e6;" | '''6''' | ||
|} | |} | ||
+ | }} | ||
Graphically, the DFA is represented as follows: | Graphically, the DFA is represented as follows: | ||
+ | {{CollapsedCode|DFA| | ||
<graph> | <graph> | ||
digraph dfa { | digraph dfa { | ||
Line 210: | Line 208: | ||
} | } | ||
</graph> | </graph> | ||
− | + | }} | |
The minimization tree is as follows: | The minimization tree is as follows: | ||
− | [[image:aula3p4mintree.jpg]] | + | {{CollapsedCode|Minimization tree| |
+ | [[image:aula3p4mintree.jpg|200]] | ||
+ | }} | ||
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). | 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). | ||
Line 219: | Line 219: | ||
Given the minimization tree above, the final minimal DFA is as follows: | Given the minimization tree above, the final minimal DFA is as follows: | ||
+ | {{CollapsedCode|Minimal DFA| | ||
<graph> | <graph> | ||
digraph dfamin { | digraph dfamin { | ||
Line 238: | Line 239: | ||
} | } | ||
</graph> | </graph> | ||
− | + | }} | |
− | |||
− | |||
− | |||
[[category:Compiladores]] | [[category:Compiladores]] |
Contents |
==Problem?? Use Thompson's algorithm to build the NFA for the following regular expression. Build the corresponding DFA and minimize it.
The non-deterministic finite automaton (NFA), built by applying Thompson's algorithm to the regular expression (a|b)*abb(a|b)* is the following:
NFA |
---|
|
Applying the determination algorithm to the above NFA, the following determination table is obtained:
Determination table |
---|
{ |
Graphically, the DFA is represented as follows:
DFA |
---|
|
The minimization tree is as follows:
Minimization tree |
---|
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 as follows:
Minimal DFA |
---|
|