Use Thompson's algorithm to build the NFA for the following regular expression. Build the corresponding DFA and minimize it.
- (a*|b*)*
| Line 1: | Line 1: | ||
| + | __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: | ||
<graph> | <graph> | ||
digraph nfa { | digraph nfa { | ||
| Line 30: | Line 39: | ||
</graph> | </graph> | ||
| − | |||
| − | |||
| − | |||
| + | 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 83: | 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: | ||
| − | |||
<graph> | <graph> | ||
digraph dfa { | digraph dfa { | ||
| Line 134: | Line 139: | ||
</graph> | </graph> | ||
|} | |} | ||
| + | <!-- ====================== END OF SOLUTION ====================== --> | ||
| + | </div> | ||
| + | </div> | ||
| + | </div> | ||
[[category:Teaching]] | [[category:Teaching]] | ||
[[category:Compilers]] | [[category:Compilers]] | ||
[[en:Theoretical Aspects of Lexical Analysis]] | [[en:Theoretical Aspects of Lexical Analysis]] | ||
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:
|
The minimization tree is as follows. As can be seen, the states are indistinguishable.
|
|---|