Theoretical Aspects of Lexical Analysis/Exercise 4
From Wiki**3
< 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.
- (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 |
|---|
| b)*abb(a |
Applying the determination algorithm to the above NFA, the following determination table is obtained:
| Determination table |
|---|
| {{{2}}} |
Graphically, the DFA is represented as follows:
| DFA |
|---|
| b)*abb(a |
The minimization tree is as follows:
| Minimization tree |
|---|
|
|
Given the minimization tree above, the final minimal DFA is as follows:
| Minimal DFA |
|---|
| b)*abb(a |