(→NFA) |
|||
| Line 1: | Line 1: | ||
__NOTOC__ | __NOTOC__ | ||
| + | <div class="section-container auto" data-section> | ||
| + | <div class="section"> | ||
| + | <p class="title" data-section-title>Problem</p> | ||
| + | <div class="content" data-section-content> | ||
| + | <!-- ====================== START OF PROBLEM ====================== --> | ||
| + | Compute the non-deterministic finite automaton (NFA) by using Thompson's algorithm. Compute the minimal deterministic finite automaton (DFA).<br/>The alphabet is Σ = { a, b }. Indicate the number of processing steps for the given input string. | ||
| + | * <nowiki>G = { ab, ab*, a|b }</nowiki>, input string = abaabb | ||
| + | <!-- ====================== END OF PROBLEM ====================== --> | ||
| + | </div> | ||
| + | </div> | ||
| + | <div class="section"> | ||
| + | <p class="title" data-section-title>Solution</p> | ||
| + | <div class="content" data-section-content> | ||
| + | <!-- ====================== START OF SOLUTION ====================== --> | ||
Compute the non-deterministic finite automaton (NFA) by using Thompson's algorithm. Compute the minimal deterministic finite automaton (DFA).<br/>The alphabet is Σ = { a, b }. Indicate the number of processing steps for the given input string. | Compute the non-deterministic finite automaton (NFA) by using Thompson's algorithm. Compute the minimal deterministic finite automaton (DFA).<br/>The alphabet is Σ = { a, b }. Indicate the number of processing steps for the given input string. | ||
* <nowiki>G = { ab, ab*, a|b }</nowiki>, input string = abaabb | * <nowiki>G = { ab, ab*, a|b }</nowiki>, input string = abaabb | ||
| − | |||
| − | |||
| − | |||
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'''. | 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'''. | ||
| Line 11: | Line 22: | ||
</runphp> | </runphp> | ||
| − | + | Applying the determination algorithm to the above NFA, the following determination table is obtained: | |
| − | |||
| − | |||
{| cellspacing="2" | {| cellspacing="2" | ||
| Line 161: | Line 170: | ||
The input string ''abaabb'' is, after 9 steps, split into three tokens: '''T1''' (corresponding to lexeme ''ab''), '''T2''' (''a''), and '''T2''' (''abb''). | The input string ''abaabb'' is, after 9 steps, split into three tokens: '''T1''' (corresponding to lexeme ''ab''), '''T2''' (''a''), and '''T2''' (''abb''). | ||
| + | <!-- ====================== END OF SOLUTION ====================== --> | ||
| + | </div> | ||
| + | </div> | ||
| + | </div> | ||
[[category:Teaching]] | [[category:Teaching]] | ||
[[category:Compilers]] | [[category:Compilers]] | ||
[[en:Theoretical Aspects of Lexical Analysis]] | [[en:Theoretical Aspects of Lexical Analysis]] | ||
Problem
Compute the non-deterministic finite automaton (NFA) by using Thompson's algorithm. Compute the minimal deterministic finite automaton (DFA).
The alphabet is Σ = { a, b }. Indicate the number of processing steps for the given input string.
Solution
Compute the non-deterministic finite automaton (NFA) by using Thompson's algorithm. Compute the minimal deterministic finite automaton (DFA).
The alphabet is Σ = { a, b }. Indicate the number of processing steps for the given 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).