Theoretical Aspects of Lexical Analysis/Exercise 4: Difference between revisions
From Wiki**3
No edit summary |
No edit summary |
||
| Line 10: | Line 10: | ||
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| | {{CollapsedCode|NFA| | ||
< | <kroki lang="graphviz"> | ||
digraph nfa { | digraph nfa { | ||
{ node [shape=circle style=invis] s } | { node [shape=circle style=invis] s } | ||
| Line 46: | Line 46: | ||
fontsize=10 | fontsize=10 | ||
} | } | ||
</ | </kroki> | ||
}} | }} | ||
| Line 205: | Line 205: | ||
{{CollapsedCode|DFA| | {{CollapsedCode|DFA| | ||
< | <kroki lang="graphviz"> | ||
digraph dfa { | digraph dfa { | ||
{ node [shape=circle style=invis] s } | { node [shape=circle style=invis] s } | ||
| Line 232: | Line 232: | ||
fontsize=10 | fontsize=10 | ||
} | } | ||
</ | </kroki> | ||
}} | }} | ||
The minimization tree is as follows: | The minimization tree is as follows: | ||
| Line 245: | Line 245: | ||
{{CollapsedCode|Minimal DFA| | {{CollapsedCode|Minimal DFA| | ||
< | <kroki lang="graphviz"> | ||
digraph dfamin { | digraph dfamin { | ||
{ node [shape=circle style=invis] s } | { node [shape=circle style=invis] s } | ||
| Line 262: | Line 262: | ||
fontsize=10 | fontsize=10 | ||
} | } | ||
</ | </kroki> | ||
}} | }} | ||
Revision as of 18:26, 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)*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 |
|---|
| {{{2}}} |
Graphically, the DFA is represented as follows:
| DFA |
|---|
 |
The minimization tree is as follows:
| Minimization tree |
|---|
|
|
Given the minimization tree above, the final minimal DFA is as follows:
| Minimal DFA |
|---|
 |