Theoretical Aspects of Lexical Analysis/Exercise 6: Difference between revisions
From Wiki**3
No edit summary |
|||
| Line 9: | Line 9: | ||
State '''3''' recognizes the first expression (token '''T1'''); state '''8''' recognizes token '''T2'''; and state '''14''' recognizes token '''T3'''. | State '''3''' recognizes the first expression (token '''T1'''); state '''8''' recognizes token '''T2'''; and state '''14''' recognizes token '''T3'''. | ||
< | <kroki lang="graphviz"> | ||
digraph nfa { | digraph nfa { | ||
{ node [shape=circle style=invis] s } | { node [shape=circle style=invis] s } | ||
| Line 37: | Line 37: | ||
fontsize=10 | fontsize=10 | ||
} | } | ||
</ | </kroki> | ||
}} | }} | ||
| Line 132: | Line 132: | ||
{{CollapsedCode|Graphical representation of the DFA| | {{CollapsedCode|Graphical representation of the DFA| | ||
< | <kroki lang="graphviz"> | ||
digraph dfa { | digraph dfa { | ||
{ node [shape=circle style=invis] s } | { node [shape=circle style=invis] s } | ||
| Line 146: | Line 146: | ||
fontsize=10 | fontsize=10 | ||
} | } | ||
</ | </kroki> | ||
}} | }} | ||
| Line 152: | Line 152: | ||
Note that before considering transition behavior, states are split according to the token they recognize. | Note that before considering transition behavior, states are split according to the token they recognize. | ||
< | <kroki lang="graphviz"> | ||
digraph mintree { | digraph mintree { | ||
node [shape=none,fixedsize=true,width=0.3,fontsize=10] | node [shape=none,fixedsize=true,width=0.3,fontsize=10] | ||
| Line 166: | Line 166: | ||
fontsize=10 | fontsize=10 | ||
} | } | ||
</ | </kroki> | ||
The tree expansion for sets {0, 4} and {1, 2} was only tested for "a" (sufficient). | The tree expansion for sets {0, 4} and {1, 2} was only tested for "a" (sufficient). | ||
Latest revision as of 18:40, 26 April 2026
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.
- G = { aa, aaaa, a|b}, input string = aaabaaaaa
NFA
The following is the result of applying Thompson's algorithm.
| NFA built by Thompson's algorithm |
|---|
|
State 3 recognizes the first expression (token T1); state 8 recognizes token T2; and state 14 recognizes token T3.  |
DFA
Determination table for the above NFA:
| 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, 11, 14 | 1 (T3) |
| 0 | b | 13 | 13, 14 | 2 (T3) |
| 1 | a | 3, 6 | 3, 6 | 3 (T1) |
| 1 | b | - | - | - |
| 2 | a | - | - | - |
| 2 | b | - | - | - |
| 3 | a | 7 | 7 | 4 |
| 3 | b | - | - | - |
| 4 | a | 8 | 8 | 5 (T2) |
| 4 | b | - | - | - |
| 5 | a | - | - | - |
| 5 | b | - | - | - |
| Graphical representation of the DFA |
|---|
 |
| DFA minimization tree |
|---|
|
Note that before considering transition behavior, states are split according to the token they recognize.  The tree expansion for sets {0, 4} and {1, 2} was only tested for "a" (sufficient). Given the minimization tree, the final minimal DFA is exactly the same as the original DFA (all leaf sets are singular). |
Input Analysis
| In | Input | In+1 / Token |
|---|---|---|
| 0 | aaabaaaaa$ | 1 |
| 1 | aabaaaaa$ | 3 |
| 3 | abaaaaa$ | 4 |
| 4 | baaaaa$ | error (backtracking) |
| 3 | abaaaaa$ | T1 (aa) |
| 0 | abaaaaa$ | 1 |
| 1 | baaaaa$ | T3 (a) |
| 0 | baaaaa$ | 2 |
| 2 | aaaaa$ | T3 (b) |
| 0 | aaaaa$ | 1 |
| 1 | aaaa$ | 3 |
| 3 | aaa$ | 4 |
| 4 | aa$ | 5 |
| 5 | a$ | T2 (aaaa) |
| 0 | a$ | 1 |
| 1 | $ | T3 (a) |
The input string aaabaaaaa is, after 16 steps, split into three tokens: T1 (corresponding to lexeme aa), T3 (a), T3 (b), T2 (aaaa), and T3 (a).