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)*
(→Minimal DFA) |
|||
| Line 1: | Line 1: | ||
| − | Use Thompson's algorithm to build the NFA for the following regular expression. Build the corresponding DFA and minimize it | + | __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. | ||
| + | * '''<nowiki>(a|b)*abb(a|b)*</nowiki>''' | ||
| + | <!-- ====================== END OF PROBLEM ====================== --> | ||
| + | </div> | ||
| + | </div> | ||
| + | <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)*abb(a|b)*</nowiki>''' is the following: | ||
<graph> | <graph> | ||
digraph nfa { | digraph nfa { | ||
| Line 39: | Line 49: | ||
16 -> 17 | 16 -> 17 | ||
10 -> 17 | 10 -> 17 | ||
| − | |||
fontsize=10 | fontsize=10 | ||
| Line 46: | Line 55: | ||
</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 171: | Line 177: | ||
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''6''' | ! style="font-weight: normal; align: center; background: #e6e6e6;" | '''6''' | ||
|} | |} | ||
| − | |||
Graphically, the DFA is represented as follows: | Graphically, the DFA is represented as follows: | ||
| − | |||
<graph> | <graph> | ||
digraph dfa { | digraph dfa { | ||
| Line 204: | Line 208: | ||
} | } | ||
</graph> | </graph> | ||
| − | |||
| − | |||
The minimization tree is as follows. | The minimization tree is as follows. | ||
| − | |||
<graph> | <graph> | ||
digraph mintree { | digraph mintree { | ||
| Line 244: | Line 245: | ||
} | } | ||
</graph> | </graph> | ||
| + | <!-- ====================== END OF SOLUTION ====================== --> | ||
| + | </div> | ||
| + | </div> | ||
| + | </div> | ||
| − | [[ | + | [[category:Teaching]] |
| + | [[category:Compilers]] | ||
| + | [[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)*abb(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, 4, 7 | 0 |
| 0 | a | 3, 8 | 1, 2, 3, 4, 6, 7, 8 | 1 |
| 0 | b | 5 | 1, 2, 4, 5, 6, 7 | 2 |
| 1 | a | 3, 8 | 1, 2, 3, 4, 6, 7, 8 | 1 |
| 1 | b | 5, 9 | 1, 2, 4, 5, 6, 7, 9 | 3 |
| 2 | a | 3, 8 | 1, 2, 3, 4, 6, 7, 8 | 1 |
| 2 | b | 5 | 1, 2, 4, 5, 6, 7 | 2 |
| 3 | a | 3, 8 | 1, 2, 3, 4, 6, 7, 8 | 1 |
| 3 | b | 5, 10 | 1, 2, 4, 5, 6, 7, 10, 11, 12, 14, 17 | 4 |
| 4 | a | 3, 8, 13 | 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16, 17 | 5 |
| 4 | b | 5, 15 | 1, 2, 4, 5, 6, 7, 11, 12, 14, 15, 16, 17 | 6 |
| 5 | a | 3, 8, 13 | 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16, 17 | 5 |
| 5 | b | 5, 9, 15 | 1, 2, 4, 5, 6, 7, 9, 11, 12, 14, 15, 16, 17 | 7 |
| 6 | a | 3, 8, 13 | 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16, 17 | 5 |
| 6 | b | 5, 15 | 1, 2, 4, 5, 6, 7, 11, 12, 14, 15, 16, 17 | 6 |
| 7 | a | 3, 8, 13 | 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16, 17 | 5 |
| 7 | b | 5, 10, 15 | 1, 2, 4, 5, 6, 7, 10, 11, 12, 14, 15, 16, 17 | 8 |
| 8 | a | 3, 8, 13 | 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16, 17 | 5 |
| 8 | b | 5, 15 | 1, 2, 4, 5, 6, 7, 11, 12, 14, 15, 16, 17 | 6 |
Graphically, the DFA is represented as follows:
The minimization tree is as follows.
The tree expansion for non-splitting sets has been omitted for simplicity ("a" transition for non-final states and the {0, 2} "a" and "b" transitions. The final states are all indistinguishable, regarding both "a" or "b" transitions (remember that, at this stage, we assume that individual states -- i.e., the final states -- are all indistinguishable).
Given the minimization tree above, the final minimal DFA is: