| Line 5: | Line 5: | ||
<div class="content" data-section-content> | <div class="content" data-section-content> | ||
<!-- ====================== START OF PROBLEM ====================== --> | <!-- ====================== START OF PROBLEM ====================== --> | ||
| − | Consider the lexical analyzer '''<nowiki>G = { ab, ab*, a|b }</nowiki>''', defined for the alphabet | + | Consider the lexical analyzer '''<nowiki>G = { ab, ab*, a|b }</nowiki>''', defined for the alphabet '''Σ = { a, b }'''. |
Compute the non-deterministic finite automaton (NFA) by using Thompson's algorithm. Compute the minimal deterministic finite automaton (DFA). | Compute the non-deterministic finite automaton (NFA) by using Thompson's algorithm. Compute the minimal deterministic finite automaton (DFA). | ||
| Line 17: | Line 17: | ||
<div class="content" data-section-content> | <div class="content" data-section-content> | ||
<!-- ====================== START OF SOLUTION ====================== --> | <!-- ====================== START OF SOLUTION ====================== --> | ||
| − | Consider the lexical analyzer '''<nowiki>G = { ab, ab*, a|b }</nowiki>''', defined for the alphabet | + | Consider the lexical analyzer '''<nowiki>G = { ab, ab*, a|b }</nowiki>''', defined for the alphabet '''Σ = { a, b }'''. |
Compute the non-deterministic finite automaton (NFA) by using Thompson's algorithm. Compute the minimal deterministic finite automaton (DFA). | Compute the non-deterministic finite automaton (NFA) by using Thompson's algorithm. Compute the minimal deterministic finite automaton (DFA). | ||
Problem
Consider the lexical analyzer G = { ab, ab*, a|b }, defined for the alphabet Σ = { a, b }.
Compute the non-deterministic finite automaton (NFA) by using Thompson's algorithm. Compute the minimal deterministic finite automaton (DFA).
Indicate the number of processing steps for the abaabb input string.
Solution
Consider the lexical analyzer G = { ab, ab*, a|b }, defined for the alphabet Σ = { a, b }.
Compute the non-deterministic finite automaton (NFA) by using Thompson's algorithm. Compute the minimal deterministic finite automaton (DFA).
Indicate the number of processing steps for the abaabb input string.
The following is the result of applying Thompson's algorithm. State 3 recognizes the first expression (token T1); state 8 recognizes token T2; and state 14 recognizes token T3.
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, 4, 9, 10, 12 | 0 |
| 0 | a | 2, 5, 11 | 2, 5, 6, 8, 11, 14 | 1 (T2) |
| 0 | b | 13 | 13, 14 | 2 (T3) |
| 1 | a | - | - | - |
| 1 | b | 3, 7 | 3, 6, 7, 8 | 3 (T1) |
| 2 | a | - | - | - |
| 2 | b | - | - | - |
| 3 | a | - | - | - |
| 3 | b | 7 | 6, 7, 8 | 4 (T2) |
| 4 | a | - | - | - |
| 4 | b | 7 | 6, 7, 8 | 4 (T2) |
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.
The tree expansion for non-splitting sets has been omitted for simplicity ("a" transition for final states {1, 4}).
Given the minimization tree, the final minimal DFA is exactly the same as the original DFA (all leaf sets are singular).
| In | Input | In+1 / Token |
|---|---|---|
| 0 | abaabb$ | 1 |
| 1 | baabb$ | 3 |
| 3 | aabb$ | T1 |
| 0 | aabb$ | 1 |
| 1 | abb$ | T2 |
| 0 | abb$ | 1 |
| 1 | bb$ | 3 |
| 3 | b$ | 4 |
| 4 | $ | T2 |
The input string abaabb is, after 9 steps, split into three tokens: T1 (corresponding to lexeme ab), T2 (a), and T2 (abb).