Theoretical Aspects of Lexical Analysis/Exercise 1: Difference between revisions
From Wiki**3
No edit summary |
No edit summary |
||
| (15 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
__NOTOC__ | __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: | |||
{{CollapsedCode|NFA for <nowiki>(a|b)*</nowiki>| | |||
<kroki lang="graphviz"> | |||
digraph nfa { | digraph nfa { | ||
{ node [shape=circle style=invis] start } | { node [shape=circle style=invis] start } | ||
| Line 48: | Line 36: | ||
0 -> 7 | 0 -> 7 | ||
fontsize=10 | fontsize=10 | ||
} | } | ||
</ | </kroki> | ||
}} | |||
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 105: | Line 90: | ||
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''2''' | ! style="font-weight: normal; align: center; background: #e6e6e6;" | '''2''' | ||
|} | |} | ||
{| width="100%" | {| width="100%" | ||
! 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: | ||
<kroki lang="graphviz"> | |||
< | |||
digraph dfa { | digraph dfa { | ||
{ node [shape=circle style=invis] start } | { node [shape=circle style=invis] start } | ||
| Line 124: | Line 107: | ||
2 -> 2 [label="b"] | 2 -> 2 [label="b"] | ||
fontsize=10 | fontsize=10 | ||
} | } | ||
</ | </kroki> | ||
Given the minimization tree to the right, the final minimal DFA is: | Given the minimization tree to the right, the final minimal DFA is: | ||
< | <kroki lang="graphviz"> | ||
digraph dfamin { | digraph dfamin { | ||
{ node [shape=circle style=invis] start } | { node [shape=circle style=invis] start } | ||
| Line 139: | Line 121: | ||
012 -> 012 [label="b"] | 012 -> 012 [label="b"] | ||
fontsize=10 | fontsize=10 | ||
/ | /*label="DFA for (a|b)*"*/ | ||
} | } | ||
</ | </kroki> | ||
! 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. | ! 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. | ||
< | <kroki lang="graphviz"> | ||
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 152: | Line 134: | ||
"{0, 1, 2}" -> "{0, 1, 2} " [label="a,b",fontsize=10] | "{0, 1, 2}" -> "{0, 1, 2} " [label="a,b",fontsize=10] | ||
fontsize=10 | fontsize=10 | ||
/ | /*label="Minimization tree"*/ | ||
} | } | ||
</ | </kroki> | ||
|} | |} | ||
<!-- ====================== END OF SOLUTION ====================== --> | |||
</div> | |||
</div> | |||
</div> | |||
[[category: | [[category:Compiladores]] | ||
[[category: | [[category:Ensino]] | ||
[[en:Theoretical Aspects of Lexical Analysis]] | [[en:Theoretical Aspects of Lexical Analysis]] | ||
Latest revision as of 18:22, 26 April 2026
Problem
Use Thompson's algorithm to build the NFA for the following regular expression. Build the corresponding DFA and minimize it.
- (a|b)*
Solution
The non-deterministic finite automaton (NFA), built by applying Thompson's algorithm to the regular expression (a|b)* is the following:
| NFA for (a|b)* |
|---|
 |
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, 4, 7 | 0 |
| 0 | a | 3 | 1, 2, 3, 4, 6, 7 | 1 |
| 0 | b | 5 | 1, 2, 4, 5, 6, 7 | 2 |
| 1 | a | 3 | 1, 2, 3, 4, 6, 7 | 1 |
| 1 | b | 5 | 1, 2, 4, 5, 6, 7 | 2 |
| 2 | a | 3 | 1, 2, 3, 4, 6, 7 | 1 |
| 2 | b | 5 | 1, 2, 4, 5, 6, 7 | 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.
 |
|---|