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: