(→DFA) |
|||
| (One intermediate revision by the same user not shown) | |||
| Line 9: | Line 9: | ||
State '''5''' recognizes the first expression (token '''T1'''); state '''13''' recognizes token '''T2'''; and state '''18''' recognizes token '''T3'''. | State '''5''' recognizes the first expression (token '''T1'''); state '''13''' recognizes token '''T2'''; and state '''18''' recognizes token '''T3'''. | ||
| − | < | + | <dot-hack> |
digraph nfa { | digraph nfa { | ||
{ node [shape=circle style=invis] s } | { node [shape=circle style=invis] s } | ||
| Line 47: | Line 47: | ||
fontsize=10 | fontsize=10 | ||
} | } | ||
| − | </ | + | </dot-hack> |
== DFA == | == DFA == | ||
| Line 195: | Line 195: | ||
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 225: | Line 225: | ||
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 237: | Line 237: | ||
"{0, 1, 2, 3, 4, 5, 6} " -> "{0, 3, 4}" [label=" T2",fontsize=10] | "{0, 1, 2, 3, 4, 5, 6} " -> "{0, 3, 4}" [label=" T2",fontsize=10] | ||
"{0, 1, 2, 3, 4, 5, 6} " -> "{2, 6}" [label=" T3",fontsize=10] | "{0, 1, 2, 3, 4, 5, 6} " -> "{2, 6}" [label=" T3",fontsize=10] | ||
| − | "{1, 5}" -> "{1}" | + | "{1, 5}" -> "{1}" |
"{1, 5}" -> "{5}" [label=" a",fontsize=10] | "{1, 5}" -> "{5}" [label=" a",fontsize=10] | ||
| − | "{0, 3, 4}" -> "{0}" | + | "{0, 3, 4}" -> "{0}" |
"{0, 3, 4}" -> "{3, 4}" [label=" a",fontsize=10] | "{0, 3, 4}" -> "{3, 4}" [label=" a",fontsize=10] | ||
"{3, 4}" -> "{3, 4} " [label=" a,b,c",fontsize=10] | "{3, 4}" -> "{3, 4} " [label=" a,b,c",fontsize=10] | ||
"{2, 6}" -> "{2, 6} " [label=" a,b,c",fontsize=10] | "{2, 6}" -> "{2, 6} " [label=" a,b,c",fontsize=10] | ||
fontsize=10 | fontsize=10 | ||
| − | |||
} | } | ||
| − | </ | + | </dot-hack> |
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 267: | Line 266: | ||
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, c }. Indicate the number of processing steps for the given input string.
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 18 recognizes token T3.
Determination table for the above NFA:
| In | α∈Σ | move(In, α) | ε-closure(move(In, α)) | In+1 = ε-closure(move(In, α)) |
|---|---|---|---|---|
| - | - | 0 | 0, 1, 6, 7, 8, 10, 13, 14 | 0 (T2) |
| 0 | a | 2, 9 | 2, 3, 5, 7, 8, 9, 10, 12, 13 | 1 (T1) |
| 0 | b | 15 | 15, 16, 18 | 2 (T3) |
| 0 | c | 11 | 7, 8, 10, 11, 12, 13 | 3 (T2) |
| 1 | a | 9 | 7, 8, 9, 10, 12, 13 | 4 (T2) |
| 1 | b | 4 | 3, 4, 5 | 5 (T1) |
| 1 | c | 11 | 7, 8, 10, 11, 12, 13 | 3 (T2) |
| 2 | a | - | - | - |
| 2 | b | - | - | - |
| 2 | c | 17 | 16, 17, 18 | 6 (T3) |
| 3 | a | 9 | 7, 8, 9, 10, 12, 13 | 4 (T2) |
| 3 | b | - | - | - |
| 3 | c | 11 | 7, 8, 10, 11, 12, 13 | 3 (T2) |
| 4 | a | 9 | 7, 8, 9, 10, 12, 13 | 4 (T2) |
| 4 | b | - | - | - |
| 4 | c | 11 | 7, 8, 10, 11, 12, 13 | 3 (T2) |
| 5 | a | - | - | - |
| 5 | b | 4 | 3, 4, 5 | 5 (T1) |
| 5 | c | - | - | - |
| 6 | - | - | - | - |
| 6 | b | - | - | - |
| 6 | c | 17 | 16, 17, 18 | 6 (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.
| In | Input | In+1 / Token |
|---|---|---|
| 0 | abbcac$ | 1 |
| 1 | bbcac$ | 5 |
| 5 | bcac$ | 5 |
| 5 | cac$ | T1 (abb) |
| 0 | cac$ | 34 |
| 34 | ac$ | 34 |
| 34 | c$ | 34 |
| 34 | $ | T2 (cac) |
The input string abbcac is, after 8 steps, split into two tokens: T1 (corresponding to lexeme abb), and T2 (cac).