Theoretical Aspects of Lexical Analysis/Exercise 3: Difference between revisions
From Wiki**3
No edit summary |
No edit summary |
||
| (2 intermediate revisions by the same user not shown) | |||
| Line 16: | Line 16: | ||
<!-- ====================== START OF SOLUTION ====================== --> | <!-- ====================== 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: | The non-deterministic finite automaton (NFA), built by applying Thompson's algorithm to the regular expression '''<nowiki>((ε|a)b)*</nowiki>''' is the following: | ||
< | <kroki lang="graphviz"> | ||
digraph nfa { | digraph nfa { | ||
{ node [shape=circle style=invis] start } | { node [shape=circle style=invis] start } | ||
| Line 32: | Line 32: | ||
7 -> 1; 7 -> 8 | 7 -> 1; 7 -> 8 | ||
fontsize=10 | fontsize=10 | ||
} | } | ||
</ | </kroki> | ||
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: | ||
| Line 90: | 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: | ||
< | <kroki lang="graphviz"> | ||
digraph dfa { | digraph dfa { | ||
{ node [shape=circle style=invis] start } | { node [shape=circle style=invis] start } | ||
| Line 103: | Line 102: | ||
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 119: | Line 117: | ||
1 -> 02 [label="b"] | 1 -> 02 [label="b"] | ||
fontsize=10 | fontsize=10 | ||
} | } | ||
</ | </kroki> | ||
! 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. | ||
< | <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 132: | Line 129: | ||
"{0, 2}" -> "{0,2} " [label=" a,b",fontsize=10] | "{0, 2}" -> "{0,2} " [label=" a,b",fontsize=10] | ||
fontsize=10 | fontsize=10 | ||
} | } | ||
</ | </kroki> | ||
|} | |} | ||
<!-- ====================== END OF SOLUTION ====================== --> | <!-- ====================== END OF SOLUTION ====================== --> | ||
| Line 141: | Line 137: | ||
</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:24, 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:
HTTP-Response:
error code: 1015
Diagram-Code:
digraph nfa {
{ node [shape=circle style=invis] start }
rankdir=LR; ratio=0.5
node [shape=doublecircle,fixedsize=true,width=0.2,fontsize=10]; 8
node [shape=circle,fixedsize=true,width=0.2,fontsize=10];
start -> 0
0 -> 1; 0 -> 8
1 -> 2; 1 -> 4
2 -> 3;
3 -> 6
4 -> 5 [label="a",fontsize=10]
5 -> 6
6 -> 7 [label="b",fontsize=10]
7 -> 1; 7 -> 8
fontsize=10
}
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:
HTTP-Response:
error code: 1015
Diagram-Code:
digraph dfa {
{ node [shape=circle style=invis] start }
rankdir=LR; ratio=0.5
node [shape=doublecircle,fixedsize=true,width=0.2,fontsize=10]; 0 2
node [shape=circle,fixedsize=true,width=0.2,fontsize=10];
start -> 0
0 -> 1 [label="a"]
0 -> 2 [label="b"]
1 -> 2 [label="b"]
2 -> 1 [label="a"]
2 -> 2 [label="b"]
fontsize=10
}
Given the minimization tree to the right, the final minimal DFA is: HTTP-Response:
error code: 1015
Diagram-Code:
digraph dfamin {
{ node [shape=circle style=invis] start }
rankdir=LR; ratio=0.5
node [shape=doublecircle,fixedsize=true,width=0.3,fontsize=10]; 02
node [shape=circle,fixedsize=true,width=0.2,fontsize=10]; 1
start -> 02
02 -> 1 [label="a"]
02 -> 02 [label="b"]
1 -> 02 [label="b"]
fontsize=10
}
|
The minimization tree is as follows.
HTTP-Response:
error code: 1015
Diagram-Code:
digraph mintree {
node [shape=none,fixedsize=true,width=0.2,fontsize=10]
"{0, 1, 2}" -> "{1}" [label="NF",fontsize=10]
"{0, 1, 2}" -> "{0, 2}" [label=" F",fontsize=10]
"{0, 2}" -> "{0,2} " [label=" a,b",fontsize=10]
fontsize=10
}
|
|---|