Theoretical Aspects of Lexical Analysis/Exercise 4
From Wiki**3
Problem
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)*
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:
| NFA |
|---|
 |
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 |
| Determination table |
|---|
| { |
Graphically, the DFA is represented as follows:
| DFA |
|---|
 |
The minimization tree is as follows:
| Minimization tree |
|---|
|
|
Given the minimization tree above, the final minimal DFA is as follows:
| Minimal DFA |
|---|
 |