Theoretical Aspects of Lexical Analysis/Exercise 16: Difference between revisions
From Wiki**3
No edit summary |
No edit summary |
||
| Line 7: | Line 7: | ||
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 '''21''' recognizes token '''T3'''. | 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 '''21''' recognizes token '''T3'''. | ||
< | <kroki lang="graphviz"> | ||
digraph nfa { | digraph nfa { | ||
{ node [shape=circle style=invis] s } | { node [shape=circle style=invis] s } | ||
| Line 50: | Line 50: | ||
fontsize=10 | fontsize=10 | ||
} | } | ||
</ | </kroki> | ||
== DFA == | == DFA == | ||
| Line 198: | Line 198: | ||
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 216: | Line 216: | ||
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 237: | Line 237: | ||
fontsize=10 | fontsize=10 | ||
} | } | ||
</ | </kroki> | ||
Given the minimization tree, the final minimal DFA is as follows. | Given the minimization tree, the final minimal DFA is as follows. | ||
< | <kroki lang="graphviz"> | ||
digraph dfa { | digraph dfa { | ||
{ node [shape=circle style=invis] s } | { node [shape=circle style=invis] s } | ||
| Line 258: | Line 258: | ||
fontsize=10 | fontsize=10 | ||
} | } | ||
</ | </kroki> | ||
== Input Analysis == | == Input Analysis == | ||
Latest revision as of 18:52, 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, c }. Indicate the number of processing steps for the given input string.
- G = { bc*, a*|c, a|b* }, input string = aaabcacc
NFA
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 21 recognizes token T3.
DFA
Determination table for the above NFA:
| In | α∈Σ | move(In, α) | ε-closure(move(In, α)) | In+1 = ε-closure(move(In, α)) |
|---|---|---|---|---|
| - | - | 0 | 0, 1, 6, 7, 8, 10, 11, 13, 14, 15, 17, 18, 20, 21 | 0 (T2) |
| 0 | a | 9, 16 | 8, 9, 10, 13, 16, 21 | 1 (T2) |
| 0 | b | 2, 19 | 2, 3, 5, 18, 19, 20, 21 | 2 (T1) |
| 0 | c | 12 | 12, 13 | 3 (T2) |
| 1 | a | 9 | 8, 9, 10, 13 | 4 (T2) |
| 1 | b | - | - | - |
| 1 | c | - | - | - |
| 2 | a | - | - | - |
| 2 | b | 19 | 18, 19, 20, 21 | 5 (T3) |
| 2 | c | 4 | 3, 4, 5 | 6 (T1) |
| 3 | a | - | - | - |
| 3 | b | - | - | - |
| 3 | c | - | - | - |
| 4 | a | 9 | 8, 9, 10, 13 | 4 (T2) |
| 4 | b | - | - | - |
| 4 | c | - | - | - |
| 5 | a | - | - | - |
| 5 | b | 19 | 18, 19, 20, 21 | 5 (T3) |
| 5 | c | - | - | - |
| 6 | a | - | - | - |
| 6 | b | - | - | - |
| 6 | c | 4 | 3, 4, 5 | 6 (T1) |
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.
Input Analysis
| In | Input | In+1 / Token |
|---|---|---|
| 0 | aaabcacc$ | 14 |
| 14 | aabcacc$ | 14 |
| 14 | abcacc$ | 14 |
| 14 | bcacc$ | T2 (aaa) |
| 0 | bcacc$ | 2 |
| 2 | cacc$ | 6 |
| 6 | acc$ | T1 (bc) |
| 0 | acc$ | 14 |
| 14 | cc$ | T2 (a) |
| 0 | cc$ | 3 |
| 3 | c$ | T2 (c) |
| 0 | c$ | 3 |
| 3 | $ | T2 (c) |
The input string aaabcacc is, after 13 steps, split into five tokens: T2 (corresponding to lexeme aaa), T1 (bc), T2 (a), T2 (c), T2 (c).