Compute the non-deterministic finite automaton (NFA) by using Thompson's algorithm. Compute the minimal deterministic finite automaton (DFA).
The alphabet is Σ = { a, b, c }. Indicate the number of processing steps for the given input string.
The following is the result of applying Thompson's algorithm.
State 5 recognizes the first expression (token T1); state 13 recognizes token T2; and state 18 recognizes token T3.
Determination table for the above NFA:
| In | α∈Σ | move(In, α) | ε-closure(move(In, α)) | In+1 = ε-closure(move(In, α)) |
|---|---|---|---|---|
| - | - | 0 | 0, 1, 6, 7, 8, 10, 13, 14 | 0 (T2) |
| 0 | a | 2, 9 | 2, 3, 5, 7, 8, 9, 10, 12, 13 | 1 (T1) |
| 0 | b | 15 | 15, 16, 18 | 2 (T3) |
| 0 | c | 11 | 7, 8, 10, 11, 12, 13 | 3 (T2) |
| 1 | a | 9 | 7, 8, 9, 10, 12, 13 | 4 (T2) |
| 1 | b | 4 | 3, 4, 5 | 5 (T1) |
| 1 | c | 11 | 7, 8, 10, 11, 12, 13 | 3 (T2) |
| 2 | a | - | - | - |
| 2 | b | - | - | - |
| 2 | c | 17 | 16, 17, 18 | 6 (T3) |
| 3 | a | 9 | 7, 8, 9, 10, 12, 13 | 4 (T2) |
| 3 | b | - | - | - |
| 3 | c | 11 | 7, 8, 10, 11, 12, 13 | 3 (T2) |
| 4 | a | 9 | 7, 8, 9, 10, 12, 13 | 4 (T2) |
| 4 | b | - | - | - |
| 4 | c | 11 | 7, 8, 10, 11, 12, 13 | 3 (T2) |
| 5 | a | - | - | - |
| 5 | b | 4 | 3, 4, 5 | 5 (T1) |
| 5 | c | - | - | - |
| 6 | - | - | - | - |
| 6 | b | - | - | - |
| 6 | c | 17 | 16, 17, 18 | 6 (T3) |
Graphically, the DFA is represented as follows: The minimization tree is as follows. Note that before considering transition behavior, states are split according to the token they recognize.