Theoretical Aspects of Lexical Analysis/Exercise 9: Difference between revisions
From Wiki**3
No edit summary |
No edit summary |
||
| (2 intermediate revisions by the same user not shown) | |||
| Line 7: | Line 7: | ||
The following is the result of applying Thompson's algorithm. State '''4''' recognizes the first expression (token '''T1'''); state '''9''' recognizes token '''T2'''; and state '''17''' recognizes token '''T3'''. | The following is the result of applying Thompson's algorithm. State '''4''' recognizes the first expression (token '''T1'''); state '''9''' recognizes token '''T2'''; and state '''17''' recognizes token '''T3'''. | ||
< | <kroki lang="graphviz"> | ||
digraph nfa { | digraph nfa { | ||
{ node [shape=circle style=invis] s } | { node [shape=circle style=invis] s } | ||
| Line 44: | Line 44: | ||
fontsize=10 | fontsize=10 | ||
} | } | ||
</ | </kroki> | ||
== DFA == | == DFA == | ||
| Line 138: | Line 138: | ||
Graphically, the DFA is represented as follows: | Graphically, the DFA is represented as follows: | ||
< | <kroki lang="graphviz"> | ||
digraph dfa { | digraph dfa { | ||
{ node [shape=circle style=invis] s } | { node [shape=circle style=invis] s } | ||
| Line 155: | Line 155: | ||
fontsize=10 | fontsize=10 | ||
} | } | ||
</ | </kroki> | ||
The minimization tree is as follows. Note that before considering transition behavior, states are split according to the token they recognize. | The minimization tree is as follows. 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 169: | Line 169: | ||
"{0, 1, 3}" -> "{0}" | "{0, 1, 3}" -> "{0}" | ||
"{0, 1, 3}" -> "{1,3}" [label=" b",fontsize=10] | "{0, 1, 3}" -> "{1,3}" [label=" b",fontsize=10] | ||
"{1,3}" -> "{1,3} " [label=" a,b",fontsize=10] | |||
"{2, 4}" -> "{2}" | "{2, 4}" -> "{2}" | ||
"{2, 4}" -> "{4}" [label=" b",fontsize=10] | "{2, 4}" -> "{4}" [label=" b",fontsize=10] | ||
fontsize=10 | fontsize=10 | ||
} | } | ||
</ | </kroki> | ||
Given the minimization tree, the final minimal DFA is as follows. Note that states 2 and 4 cannot be the same since they recognize different tokens. | Given the minimization tree, the final minimal DFA is as follows. Note that states 2 and 4 cannot be the same since they recognize different tokens. | ||
< | <kroki lang="graphviz"> | ||
digraph mindfa { | digraph mindfa { | ||
{ node [shape=circle style=invis] s } | { node [shape=circle style=invis] s } | ||
| Line 195: | Line 194: | ||
fontsize=10 | fontsize=10 | ||
} | } | ||
</ | </kroki> | ||
== Input Analysis == | == Input Analysis == | ||
Latest revision as of 18:43, 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 = { a*, ba*, a|b* }, input string = aababb
NFA
The following is the result of applying Thompson's algorithm. State 4 recognizes the first expression (token T1); state 9 recognizes token T2; and state 17 recognizes token T3.
DFA
Determination table for the above NFA:
| In | α∈Σ | move(In, α) | ε-closure(move(In, α)) | In+1 = ε-closure(move(In, α)) |
|---|---|---|---|---|
| - | - | 0 | 0, 1, 2, 4, 5, 10, 11, 13, 14, 16, 17 | 0 (T1) |
| 0 | a | 3, 12 | 2, 3, 4, 12, 17 | 1 (T1) |
| 0 | b | 6, 15 | 6, 7, 9, 14, 15, 16, 17 | 2 (T2) |
| 1 | a | 3 | 2, 3, 4 | 3 (T1) |
| 1 | b | - | - | - |
| 2 | a | 8 | 7, 8, 9 | 4 (T2) |
| 2 | b | 15 | 14, 15, 16, 17 | 5 (T3) |
| 3 | a | 3 | 2, 3, 4 | 3 (T1) |
| 3 | b | - | - | - |
| 4 | a | 8 | 7, 8, 9 | 4 (T2) |
| 4 | b | - | - | - |
| 5 | a | - | - | - |
| 5 | b | 15 | 14, 15, 16, 17 | 5 (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.
Given the minimization tree, the final minimal DFA is as follows. Note that states 2 and 4 cannot be the same since they recognize different tokens.
Input Analysis
| In | Input | In+1 / Token |
|---|---|---|
| 0 | aababb$ | 13 |
| 13 | ababb$ | 13 |
| 13 | babb$ | T1 (aa) |
| 0 | babb$ | 2 |
| 2 | abb$ | 4 |
| 4 | bb$ | T2 (ba) |
| 0 | bb$ | 2 |
| 2 | b$ | 5 |
| 5 | $ | T3 (bb) |
The input string aababb is, after 9 steps, split into three tokens: T1 (corresponding to lexeme aa), T2 (ba), and T3 (bb).