(→Solution) |
|||
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| | ||
− | < | + | <dot-hack> |
digraph nfa { | digraph nfa { | ||
{ node [shape=circle style=invis] s } | { node [shape=circle style=invis] s } | ||
Line 45: | Line 45: | ||
fontsize=10 | fontsize=10 | ||
− | |||
} | } | ||
− | </ | + | </dot-hack> |
}} | }} | ||
Line 206: | Line 205: | ||
{{CollapsedCode|DFA| | {{CollapsedCode|DFA| | ||
− | < | + | <dot-hack> |
digraph dfa { | digraph dfa { | ||
{ node [shape=circle style=invis] s } | { node [shape=circle style=invis] s } | ||
Line 232: | Line 231: | ||
8 -> 6 [label="b",fontsize=10] | 8 -> 6 [label="b",fontsize=10] | ||
fontsize=10 | fontsize=10 | ||
− | |||
} | } | ||
− | </ | + | </dot-hack> |
}} | }} | ||
The minimization tree is as follows: | The minimization tree is as follows: | ||
Line 247: | Line 245: | ||
{{CollapsedCode|Minimal DFA| | {{CollapsedCode|Minimal DFA| | ||
− | < | + | <dot-hack> |
digraph dfamin { | digraph dfamin { | ||
{ node [shape=circle style=invis] s } | { node [shape=circle style=invis] s } | ||
Line 263: | Line 261: | ||
45678 -> 45678 [label="b",fontsize=10] | 45678 -> 45678 [label="b",fontsize=10] | ||
fontsize=10 | fontsize=10 | ||
− | |||
} | } | ||
− | </ | + | </dot-hack> |
}} | }} | ||
Contents |
Use Thompson's algorithm to build the NFA for the following regular expression. Build the corresponding DFA and minimize it.
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 |
---|
Given the minimization tree above, the final minimal DFA is as follows:
Minimal DFA |
---|