Theoretical Aspects of Lexical Analysis/Exercise 4: Difference between revisions
From Wiki**3
No edit summary |
No edit summary |
||
| 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 07:51, 24 June 2016
==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 |
|---|
| b)*abb(a |
Applying the determination algorithm to the above NFA, the following determination table is obtained:
| Determination table |
|---|
|
{ |
Graphically, the DFA is represented as follows:
| DFA |
|---|
| b)*abb(a |
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 |
|---|
| b)*abb(a |