| 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'''. | ||
| − | < | + | <dot-hack> |
digraph nfa { | digraph nfa { | ||
{ node [shape=circle style=invis] s } | { node [shape=circle style=invis] s } | ||
| Line 44: | Line 44: | ||
fontsize=10 | fontsize=10 | ||
} | } | ||
| − | </ | + | </dot-hack> |
== DFA == | == DFA == | ||
| Line 138: | Line 138: | ||
Graphically, the DFA is represented as follows: | Graphically, the DFA is represented as follows: | ||
| − | < | + | <dot-hack> |
digraph dfa { | digraph dfa { | ||
{ node [shape=circle style=invis] s } | { node [shape=circle style=invis] s } | ||
| Line 155: | Line 155: | ||
fontsize=10 | fontsize=10 | ||
} | } | ||
| − | </ | + | </dot-hack> |
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. | ||
| − | < | + | <dot-hack> |
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 167: | Line 167: | ||
"{0, 1, 2, 3, 4, 5} " -> "{2, 4}" [label=" T2",fontsize=10] | "{0, 1, 2, 3, 4, 5} " -> "{2, 4}" [label=" T2",fontsize=10] | ||
"{0, 1, 2, 3, 4, 5} " -> "{5}" [label=" T3",fontsize=10] | "{0, 1, 2, 3, 4, 5} " -> "{5}" [label=" T3",fontsize=10] | ||
| − | "{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] | ||
| − | "{2, 4}" -> "{2}" | + | "{2, 4}" -> "{2}" |
"{2, 4}" -> "{4}" [label=" b",fontsize=10] | "{2, 4}" -> "{4}" [label=" b",fontsize=10] | ||
fontsize=10 | fontsize=10 | ||
| − | |||
} | } | ||
| − | </ | + | </dot-hack> |
The tree expansion for non-splitting sets has been omitted for simplicity ("a" transitions for super-state {0, 1, 3}, and "a" and "b" transitions for super-state {1,3}). | The tree expansion for non-splitting sets has been omitted for simplicity ("a" transitions for super-state {0, 1, 3}, and "a" and "b" transitions for super-state {1,3}). | ||
| Line 180: | Line 179: | ||
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. | ||
| − | < | + | <dot-hack> |
digraph mindfa { | digraph mindfa { | ||
{ node [shape=circle style=invis] s } | { node [shape=circle style=invis] s } | ||
| Line 196: | Line 195: | ||
fontsize=10 | fontsize=10 | ||
} | } | ||
| − | </ | + | </dot-hack> |
== Input Analysis == | == Input Analysis == | ||
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 4 recognizes the first expression (token T1); state 9 recognizes token T2; and state 17 recognizes token T3.
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.
The tree expansion for non-splitting sets has been omitted for simplicity ("a" transitions for super-state {0, 1, 3}, and "a" and "b" transitions for super-state {1,3}).
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.
| 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).