Difference between revisions of "Theoretical Aspects of Lexical Analysis/Exercise 4"
From Wiki**3
< Theoretical Aspects of Lexical Analysis
| 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]] | ||
Revision as of 09:51, 24 June 2016
Contents |
==Problem?? Use Thompson's algorithm to build the NFA for the following regular expression. Build the corresponding DFA and minimize it.
- (a|b)*abb(a|b)*
Solution
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 |
|---|
|
|