(→NFA) |
(→NFA) |
||
Line 45: | Line 45: | ||
<runphp> | <runphp> | ||
− | echo '<div id="mynetwork" style="height: 600px;"></div><script type="text/javascript">var container = document.getElementById("mynetwork"); var options = { nodes: { color: { background: "white", border: "#2B7CE9" }, shape: "dot", radius: 30 }, hierarchicalLayout: { layout: "direction" } }; var data = { dot: \'digraph { { node [shape=circle,style=invis] s } node [shape=doublecircle,line=red,color=yellow] 3 8 14; node [shape=circle]; s -> 0; 0 -> 1; 1 -> 2 [label="a"]; 2 -> 3 [label="b"]; 0 -> 4; 4 -> 5 [label="a"]; 5 -> 6; 5 -> 8; 6 -> 7 [label="b"]; 7 -> 6; 7 -> 8; 0 -> 9; 9 -> 10; 9 -> 12; 10 -> 11 [label="a"]; 12 -> 13 [label="b"]; 11 -> 14; 13 -> 14; }\' }; var network = new vis.Network(container, data, options);</script>'; | + | echo '<div id="mynetwork" style="height: 600px;"></div><script type="text/javascript">var container = document.getElementById("mynetwork"); var options = { nodes: { color: { background: "white", border: "#2B7CE9" }, shape: "dot", radius: 30 }, hierarchicalLayout: { layout: "direction" } }; var data = { dot: \'digraph { { node [shape=circle,style=invis] s }; { node [shape=doublecircle,line=red,color=yellow] 3 8 14}; { node [shape=circle] }; s -> 0; 0 -> 1; 1 -> 2 [label="a"]; 2 -> 3 [label="b"]; 0 -> 4; 4 -> 5 [label="a"]; 5 -> 6; 5 -> 8; 6 -> 7 [label="b"]; 7 -> 6; 7 -> 8; 0 -> 9; 9 -> 10; 9 -> 12; 10 -> 11 [label="a"]; 12 -> 13 [label="b"]; 11 -> 14; 13 -> 14; }\' }; var network = new vis.Network(container, data, options);</script>'; |
+ | </runphp> | ||
+ | |||
+ | == NFA == | ||
+ | |||
+ | The following is the result of applying Thompson's algorithm. State '''3''' recognizes the first expression (token '''T1'''); state '''8''' recognizes token '''T2'''; and state '''14''' recognizes token '''T3'''. | ||
+ | |||
+ | <runphp> | ||
+ | echo '<div id="mynetwork2" style="height: 600px;"></div><script type="text/javascript">var container = document.getElementById("mynetwork"); | ||
+ | |||
+ | var nodes = [ | ||
+ | {id: 99, label: "s"}, | ||
+ | {id: 0, label: "0"}, | ||
+ | {id: 1, label: "1"}, | ||
+ | {id: 2, label: "2"}, | ||
+ | {id: 3, label: "3final"}, | ||
+ | {id: 4, label: "4"}, | ||
+ | {id: 5, label: "5"} | ||
+ | {id: 6, label: "6"}, | ||
+ | {id: 7, label: "7"} | ||
+ | {id: 8, label: "8final"}, | ||
+ | {id: 9, label: "9"} | ||
+ | {id: 10, label: "10"}, | ||
+ | {id: 11, label: "11"} | ||
+ | {id: 12, label: "12"}, | ||
+ | {id: 13, label: "13"} | ||
+ | {id: 14, label: "14final"} | ||
+ | ]; | ||
+ | var edges = [ | ||
+ | {from: 1, to: 2}, | ||
+ | {from: 1, to: 3}, | ||
+ | {from: 2, to: 4}, | ||
+ | {from: 2, to: 5} | ||
+ | ]; | ||
+ | |||
+ | var options = { nodes: { color: { background: "white", border: "#2B7CE9" }, shape: "circle", radius: 30 }, hierarchicalLayout: { layout: "direction" } }; var data = { dot: \'digraph { { 3 8 14; node [shape=circle]; s -> 0; 0 -> 1; 1 -> 2 [label="a"]; 2 -> 3 [label="b"]; 0 -> 4; 4 -> 5 [label="a"]; 5 -> 6; 5 -> 8; 6 -> 7 [label="b"]; 7 -> 6; 7 -> 8; 0 -> 9; 9 -> 10; 9 -> 12; 10 -> 11 [label="a"]; 12 -> 13 [label="b"]; 11 -> 14; 13 -> 14; }\' }; var network = new vis.Network(container, data, options);</script>'; | ||
</runphp> | </runphp> | ||
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 3 recognizes the first expression (token T1); state 8 recognizes token T2; and state 14 recognizes token T3.
The following is the result of applying Thompson's algorithm. State 3 recognizes the first expression (token T1); state 8 recognizes token T2; and state 14 recognizes token T3.
The following is the result of applying Thompson's algorithm. State 3 recognizes the first expression (token T1); state 8 recognizes token T2; and state 14 recognizes token T3.
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, 6, 8, 11, 14 | 1 (T2) |
0 | b | 13 | 13, 14 | 2 (T3) |
1 | a | - | - | - |
1 | b | 3, 7 | 3, 6, 7, 8 | 3 (T1) |
2 | a | - | - | - |
2 | b | - | - | - |
3 | a | - | - | - |
3 | b | 7 | 6, 7, 8 | 4 (T2) |
4 | a | - | - | - |
4 | b | 7 | 6, 7, 8 | 4 (T2) |
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" transition for final states {1, 4}).
Given the minimization tree, the final minimal DFA is exactly the same as the original DFA (all leaf sets are singular).
In | Input | In+1 / Token |
---|---|---|
0 | abaabb$ | 1 |
1 | baabb$ | 3 |
3 | aabb$ | T1 |
0 | aabb$ | 1 |
1 | abb$ | T2 |
0 | abb$ | 1 |
1 | bb$ | 3 |
3 | b$ | 4 |
4 | $ | T2 |
The input string abaabb is, after 9 steps, split into three tokens: T1 (corresponding to lexeme ab), T2 (a), and T2 (abb).