Use Thompson's algorithm to build the NFA for the following regular expression. Build the corresponding DFA and minimize it.
- ((ε|a)b)*
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, 4, 6, 8 | 0 |
| 0 | a | 5 | 5, 6 | 1 |
| 0 | b | 7 | 1, 2, 3, 4, 6, 7, 8 | 2 |
| 1 | a | - | - | - |
| 1 | b | 7 | 1, 2, 3, 4, 6, 7, 8 | 2 |
| 2 | a | 5 | 5, 6 | 1 |
| 2 | b | 7 | 1, 2, 3, 4, 6, 7, 8 | 2 |
| Graphically, the DFA is represented as follows:
Given the minimization tree to the right, the final minimal DFA is: |
The minimization tree is as follows. |
|---|