Use Thompson's algorithm to build the NFA for the following regular expression. Build the corresponding DFA and minimize it.
- (a*|b*)*
Line 144: | Line 144: | ||
</div> | </div> | ||
− | [[category: | + | [[category:Compiladores]] |
− | [[category: | + | [[category:Ensino]] |
+ | |||
[[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.
|
---|