Use Thompson's algorithm to build the NFA for the following regular expression. Build the corresponding DFA and minimize it.
- (a*|b*)*
| 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: | ||
| − | < | + | <dot-hack> |
digraph nfa { | digraph nfa { | ||
{ node [shape=circle style=invis] start } | { node [shape=circle style=invis] start } | ||
| Line 35: | Line 35: | ||
10 -> 1; 10 -> 11 | 10 -> 1; 10 -> 11 | ||
fontsize=10 | fontsize=10 | ||
| − | |||
} | } | ||
| − | </ | + | </dot-hack> |
| − | |||
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 93: | Line 91: | ||
{| 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: | ||
| − | < | + | <dot-hack> |
digraph dfa { | digraph dfa { | ||
{ node [shape=circle style=invis] start } | { node [shape=circle style=invis] start } | ||
| Line 107: | Line 105: | ||
2 -> 2 [label="b"] | 2 -> 2 [label="b"] | ||
fontsize=10 | fontsize=10 | ||
| − | |||
} | } | ||
| − | </ | + | </dot-hack> |
Given the minimization tree to the right, the final minimal DFA is: | Given the minimization tree to the right, the final minimal DFA is: | ||
| − | < | + | <dot-hack> |
digraph dfamin { | digraph dfamin { | ||
{ node [shape=circle style=invis] start } | { node [shape=circle style=invis] start } | ||
| Line 122: | Line 119: | ||
012 -> 012 [label="b"] | 012 -> 012 [label="b"] | ||
fontsize=10 | fontsize=10 | ||
| − | |||
} | } | ||
| − | </ | + | </dot-hack> |
! 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. | ||
| − | < | + | <dot-hack> |
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 135: | Line 131: | ||
"{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 | ||
| − | |||
} | } | ||
| − | </ | + | </dot-hack> |
|} | |} | ||
<!-- ====================== END OF SOLUTION ====================== --> | <!-- ====================== END OF SOLUTION ====================== --> | ||
Problem
Use Thompson's algorithm to build the NFA for the following regular expression. Build the corresponding DFA and minimize it.
Solution
The non-deterministic finite automaton (NFA), built by applying Thompson's algorithm to the regular expression (a*|b*)* is the following:
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, 5, 6, 7, 9, 10, 11 | 0 |
| 0 | a | 4 | 1, 2, 3, 4, 5, 6, 7, 9, 10, 11 | 1 |
| 0 | b | 8 | 1, 2, 3, 5, 6, 7, 8, 9, 10, 11 | 2 |
| 1 | a | 4 | 1, 2, 3, 4, 5, 6, 7, 9, 10, 11 | 1 |
| 1 | b | 8 | 1, 2, 3, 5, 6, 7, 8, 9, 10, 11 | 2 |
| 2 | a | 4 | 1, 2, 3, 4, 5, 6, 7, 9, 10, 11 | 1 |
| 2 | b | 8 | 1, 2, 3, 5, 6, 7, 8, 9, 10, 11 | 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. |
|---|