(→DFA) |
|||
| (46 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
__NOTOC__ | __NOTOC__ | ||
| − | Compute the non-deterministic finite automaton (NFA) by using Thompson's algorithm. Compute the minimal deterministic finite automaton (DFA). | + | Consider the lexical analyzer '''<nowiki>G = { ab, ab*, a|b }</nowiki>''', defined for the alphabet '''Σ = { a, b }'''. |
| − | + | ||
| + | Compute the non-deterministic finite automaton (NFA) by using Thompson's algorithm. Compute the minimal deterministic finite automaton (DFA). | ||
| + | |||
| + | Indicate the number of processing steps for the '''abaabb''' input string. | ||
== NFA == | == NFA == | ||
| Line 7: | Line 10: | ||
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'''. | ||
| + | <dot-hack> | ||
| + | digraph nfa { | ||
| + | { node [shape=circle style=invis] s } | ||
| + | rankdir=LR; ratio=0.5 | ||
| + | node [shape=doublecircle,fixedsize=true,width=0.2,fontsize=10]; 3 8 14 | ||
| + | node [shape=circle,fixedsize=true,width=0.2,fontsize=10]; | ||
| + | |||
| + | s -> 0 | ||
| + | |||
| + | 0 -> 1 | ||
| + | 1 -> 2 [label="a",fontsize=10] | ||
| + | 2 -> 3 [label="b",fontsize=10] | ||
| + | |||
| + | 0 -> 4 | ||
| + | 4 -> 5 [label="a",fontsize=10] | ||
| + | 5 -> 6 | ||
| + | 5 -> 8 | ||
| + | 6 -> 7 [label="b",fontsize=10] | ||
| + | 7 -> 6 | ||
| + | 7 -> 8 | ||
| + | |||
| + | 0 -> 9 | ||
| + | 9 -> 10 | ||
| + | 9 -> 12 | ||
| + | 10 -> 11 [label="a",fontsize=10] | ||
| + | 12 -> 13 [label="b",fontsize=10] | ||
| + | 11 -> 14 | ||
| + | 13 -> 14 | ||
| + | fontsize=10 | ||
| + | } | ||
| + | </dot-hack> | ||
| + | <!-- | ||
<runphp> | <runphp> | ||
| − | + | print '<div id="mynetwork2" style="height: 400px;"></div><script type="text/javascript">var container = document.getElementById("mynetwork2"); var nodes = [ {id: 0, label: "0", group: "all", level: 1}, {id: 1, label: "1", level: 2, group: "t1"}, {id: 2, label: "2", level: 3, group: "t1"}, {id: 3, label: "3", level: 4, borderWidth: 3, group: "t1"}, {id: 4, label: "4", level: 2, group: "t2"}, {id: 5, label: "5", level: 3, group: "t2"}, {id: 6, label: "6", level: 4, group: "t2"}, {id: 7, label: "7", level: 5, group: "t2"}, {id: 8, label: "8", level: 5, borderWidth: 3, group: "t2"}, {id: 9, label: "9", level: 2, group: "t3"}, {id: 10, label: "10", level: 3, group: "t3"}, {id: 11, label: "11", level: 4, group: "t3"}, {id: 12, label: "12", level: 3, group: "t3"}, {id: 13, label: "13", level: 4, group: "t3"}, {id: 14, label: "14", borderWidth: 3, level: 5, group: "t3"} ]; var edges = [ {from: 0, to: 1}, {from: 1, to: 2, label: "a" }, {from: 2, to: 3, label: "b" }, {from: 0, to: 4}, {from: 4, to: 5, label: "a" }, {from: 5, to: 6}, {from: 5, to: 8}, {from: 6, to: 7, label: "b" }, {from: 7, to: 6}, {from: 7, to: 8}, {from: 0, to: 9}, {from: 9, to: 10}, {from: 9, to: 12}, {from: 10, to: 11, label: "a" }, {from: 12, to: 13, label: "b" }, {from: 11, to: 14}, {from: 13, to: 14}, ]; var options = { groups: { t1: { color: { border: "#41a906", background: "#7be141", highlight: { border: "#41a906", background: "#7be141", } } }, t2: { color: { border: "#f31d22", background: "#fa8a8c", highlight: { border: "#f31d22", background: "#fa8a8c", } } }, t3: { color: { border: "#ffa500", background: "#ffff00", highlight: { border: "#ffa500", background: "#ffff00", } } } }, edges: { style: "arrow" }, nodes: { color: { background: "white", border: "#2B7CE9" }, radius: 30 }, hierarchicalLayout: { direction: "LR" }, zoomable: false }; var data = { nodes: nodes, edges: edges }; var network = new vis.Network(container, data, options);</script>'; | |
</runphp> | </runphp> | ||
| + | --> | ||
== DFA == | == DFA == | ||
| − | + | Applying the determination algorithm to the above NFA, the following determination table is obtained: | |
{| cellspacing="2" | {| cellspacing="2" | ||
| Line 22: | Line 58: | ||
! style="padding-left: 20px; padding-right: 20px; background: wheat;" | I<sub>n+1</sub> = ε-closure(move(I<sub>n</sub>, α)) | ! style="padding-left: 20px; padding-right: 20px; background: wheat;" | I<sub>n+1</sub> = ε-closure(move(I<sub>n</sub>, α)) | ||
|- | |- | ||
| − | ! style="font-weight: normal; align: center; background: #ffffcc;" | - | + | ! style="font-weight: normal; align: center; background: #ffffcc;" | - |
| − | ! style="font-weight: normal; align: center; background: #ffffcc;" | - | + | ! style="font-weight: normal; align: center; background: #ffffcc;" | - |
! style="font-weight: normal; align: center; background: #ffffcc;" | 0 | ! style="font-weight: normal; align: center; background: #ffffcc;" | 0 | ||
! style="font-weight: normal; align: left; background: #ffffcc;" | 0, 1, 4, 9, 10, 12 | ! style="font-weight: normal; align: left; background: #ffffcc;" | 0, 1, 4, 9, 10, 12 | ||
| Line 29: | Line 65: | ||
|- | |- | ||
! style="font-weight: normal; align: center; background: #e6e6e6;" | 0 | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 0 | ||
| − | ! style="font-weight: normal; align: center; background: #e6e6e6;" | a | + | ! style="font-weight: normal; align: center; background: #e6e6e6;" | a |
! style="font-weight: normal; align: center; background: #e6e6e6;" | 2, 5, 11 | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 2, 5, 11 | ||
! style="font-weight: normal; align: left; background: #e6e6e6;" | 2, 5, 6, '''8''', 11, '''14''' | ! style="font-weight: normal; align: left; background: #e6e6e6;" | 2, 5, 6, '''8''', 11, '''14''' | ||
| Line 35: | Line 71: | ||
|- | |- | ||
! style="font-weight: normal; align: center; background: #e6e6e6;" | 0 | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 0 | ||
| − | ! style="font-weight: normal; align: center; background: #e6e6e6;" | b | + | ! style="font-weight: normal; align: center; background: #e6e6e6;" | b |
! style="font-weight: normal; align: center; background: #e6e6e6;" | 13 | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 13 | ||
! style="font-weight: normal; align: left; background: #e6e6e6;" | 13, '''14''' | ! style="font-weight: normal; align: left; background: #e6e6e6;" | 13, '''14''' | ||
| Line 41: | Line 77: | ||
|- | |- | ||
! style="font-weight: normal; align: center; background: #ffffcc;" | 1 | ! style="font-weight: normal; align: center; background: #ffffcc;" | 1 | ||
| − | ! style="font-weight: normal; align: center; background: #ffffcc;" | a | + | ! style="font-weight: normal; align: center; background: #ffffcc;" | a |
! style="font-weight: normal; align: center; background: #ffffcc;" | - | ! style="font-weight: normal; align: center; background: #ffffcc;" | - | ||
! style="font-weight: normal; align: left; background: #ffffcc;" | - | ! style="font-weight: normal; align: left; background: #ffffcc;" | - | ||
! style="font-weight: normal; align: center; background: #ffffcc;" | - | ! style="font-weight: normal; align: center; background: #ffffcc;" | - | ||
|- | |- | ||
| − | ! style="font-weight: normal; align: center; background: #ffffcc;" | 1 | + | ! style="font-weight: normal; align: center; background: #ffffcc;" | 1 |
| − | ! style="font-weight: normal; align: center; background: #ffffcc;" | b | + | ! style="font-weight: normal; align: center; background: #ffffcc;" | b |
! style="font-weight: normal; align: center; background: #ffffcc;" | '''3''', 7 | ! style="font-weight: normal; align: center; background: #ffffcc;" | '''3''', 7 | ||
! style="font-weight: normal; align: left; background: #ffffcc;" | '''3''', 6, 7, '''8''' | ! style="font-weight: normal; align: left; background: #ffffcc;" | '''3''', 6, 7, '''8''' | ||
| Line 59: | Line 95: | ||
|- | |- | ||
! style="font-weight: normal; align: center; background: #e6e6e6;" | 2 | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 2 | ||
| − | ! style="font-weight: normal; align: center; background: #e6e6e6;" | b | + | ! style="font-weight: normal; align: center; background: #e6e6e6;" | b |
! style="font-weight: normal; align: center; background: #e6e6e6;" | - | ! style="font-weight: normal; align: center; background: #e6e6e6;" | - | ||
! style="font-weight: normal; align: left; background: #e6e6e6;" | - | ! style="font-weight: normal; align: left; background: #e6e6e6;" | - | ||
| Line 71: | Line 107: | ||
|- | |- | ||
! style="font-weight: normal; align: center; background: #ffffcc;" | 3 | ! style="font-weight: normal; align: center; background: #ffffcc;" | 3 | ||
| − | ! style="font-weight: normal; align: center; background: #ffffcc;" | b | + | ! style="font-weight: normal; align: center; background: #ffffcc;" | b |
! style="font-weight: normal; align: center; background: #ffffcc;" | 7 | ! style="font-weight: normal; align: center; background: #ffffcc;" | 7 | ||
! style="font-weight: normal; align: left; background: #ffffcc;" | 6, 7, '''8''' | ! style="font-weight: normal; align: left; background: #ffffcc;" | 6, 7, '''8''' | ||
| Line 83: | Line 119: | ||
|- | |- | ||
! style="font-weight: normal; align: center; background: #e6e6e6;" | 4 | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 4 | ||
| − | ! style="font-weight: normal; align: center; background: #e6e6e6;" | b | + | ! style="font-weight: normal; align: center; background: #e6e6e6;" | b |
! style="font-weight: normal; align: center; background: #e6e6e6;" | 7 | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 7 | ||
! style="font-weight: normal; align: left; background: #e6e6e6;" | 6, 7, '''8''' | ! style="font-weight: normal; align: left; background: #e6e6e6;" | 6, 7, '''8''' | ||
| Line 90: | Line 126: | ||
Graphically, the DFA is represented as follows: | Graphically, the DFA is represented as follows: | ||
| − | + | <dot-hack> | |
| + | digraph dfa { | ||
| + | { node [shape=circle style=invis] s } | ||
| + | rankdir=LR; ratio=0.5 | ||
| + | node [shape=doublecircle,fixedsize=true,width=0.2,fontsize=10]; 1 2 3 4 | ||
| + | node [shape=circle,fixedsize=true,width=0.2,fontsize=10]; | ||
| + | s -> 0 | ||
| + | 0 -> 1 [label="a",fontsize=10] | ||
| + | 0 -> 2 [label="b",fontsize=10] | ||
| + | 1 -> 3 [label="b",fontsize=10] | ||
| + | 3 -> 4 [label="b",fontsize=10] | ||
| + | 4 -> 4 [label="b",fontsize=10] | ||
| + | fontsize=10 | ||
| + | } | ||
| + | </dot-hack> | ||
| + | <!-- | ||
<runphp> | <runphp> | ||
| − | echo | + | echo<<<___EOT___ |
| + | <nowiki><div id="mydfa" style="height: 250px; width: 100%;"></div> | ||
| + | <script type="text/javascript"> | ||
| + | var container = document.getElementById("mydfa"); | ||
| + | var nodes = [ {id: 0, label: "0", group: "all", level: 1}, {id: 1, label: "1", level: 2, borderWidth: 4, group: "t2"}, {id: 2, label: "2", level: 2, borderWidth: 4, group: "t3"}, {id: 3, label: "3", level: 3, borderWidth: 4, group: "t1"}, {id: 4, label: "4", level: 4, borderWidth: 4, group: "t2"}, ]; | ||
| + | var edges = [ {from: 0, to: 1, label: "a" }, {from: 0, to: 2, label: "b" }, {from: 1, to: 3, label: "b" }, {from: 3, to: 4, label: "b" }, {from: 4, to: 4, label: "b" }, ]; var options = { groups: { t1: { color: { border: "#41a906", background: "#7be141", highlight: { border: "#41a906", background: "#7be141" } } }, t2: { color: { border: "#f31d22", background: "#fa8a8c", highlight: { border: "#f31d22", background: "#fa8a8c" } } }, t3: { color: { border: "#ffa500", background: "#ffff00", highlight: { border: "#ffa500", background: "#ffff00" } } } }, edges: { style: "arrow", color: { color: "black", highlight: "black" }, labelAlignment: "line-above" }, nodes: { color: { background: "white", border: "#2B7CE9" }, shape: "circle", radius: 30 }, hierarchicalLayout: { nodeSpacing: 100, direction: "LR" }, zoomable: false }; | ||
| + | var data = { nodes: nodes, edges: edges }; | ||
| + | var network = new vis.Network(container, data, options); | ||
| + | </script></nowiki> | ||
| + | ___EOT___; | ||
</runphp> | </runphp> | ||
| − | + | --> | |
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] | ||
"{0, 1, 2, 3, 4}" -> "{0}" [label="NF",fontsize=10] | "{0, 1, 2, 3, 4}" -> "{0}" [label="NF",fontsize=10] | ||
| Line 105: | Line 165: | ||
"{1, 2, 3, 4}" -> "{1, 4}" [label=" T2",fontsize=10] | "{1, 2, 3, 4}" -> "{1, 4}" [label=" T2",fontsize=10] | ||
"{1, 2, 3, 4}" -> "{2}" [label=" T3",fontsize=10] | "{1, 2, 3, 4}" -> "{2}" [label=" T3",fontsize=10] | ||
| − | "{1, 4}" -> "{1}" / | + | "{1, 4}" -> "{1}" /*[label=" T3",fontsize=10]*/ |
"{1, 4}" -> "{4}" [label=" b",fontsize=10] | "{1, 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" transition for final states {1, 4}). | The tree expansion for non-splitting sets has been omitted for simplicity ("a" transition for final states {1, 4}). | ||
| Line 124: | Line 183: | ||
|- | |- | ||
! style="font-weight: normal; align: center; background: #ffffcc;" | 0 | ! style="font-weight: normal; align: center; background: #ffffcc;" | 0 | ||
| − | ! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>abaabb$</tt> | + | ! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>abaabb$</tt> |
! style="font-weight: normal; align: center; background: #ffffcc;" | 1 | ! style="font-weight: normal; align: center; background: #ffffcc;" | 1 | ||
|- | |- | ||
! style="font-weight: normal; align: center; background: #ffffcc;" | 1 | ! style="font-weight: normal; align: center; background: #ffffcc;" | 1 | ||
| − | ! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>baabb$</tt> | + | ! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>baabb$</tt> |
! style="font-weight: normal; align: center; background: #ffffcc;" | 3 | ! style="font-weight: normal; align: center; background: #ffffcc;" | 3 | ||
|- | |- | ||
! style="font-weight: normal; align: center; background: #ffffcc;" | 3 | ! style="font-weight: normal; align: center; background: #ffffcc;" | 3 | ||
| − | ! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>aabb$</tt> | + | ! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>aabb$</tt> |
! style="font-weight: normal; align: center; background: #ffffcc;" | '''T1''' | ! style="font-weight: normal; align: center; background: #ffffcc;" | '''T1''' | ||
|- | |- | ||
| Line 162: | Line 221: | ||
The input string ''abaabb'' is, after 9 steps, split into three tokens: '''T1''' (corresponding to lexeme ''ab''), '''T2''' (''a''), and '''T2''' (''abb''). | The input string ''abaabb'' is, after 9 steps, split into three tokens: '''T1''' (corresponding to lexeme ''ab''), '''T2''' (''a''), and '''T2''' (''abb''). | ||
| − | [[category: | + | [[category:Compiladores]] |
| − | [[category: | + | [[category:Ensino]] |
| + | |||
[[en:Theoretical Aspects of Lexical Analysis]] | [[en:Theoretical Aspects of Lexical Analysis]] | ||
Consider the lexical analyzer G = { ab, ab*, a|b }, defined for the alphabet Σ = { a, b }.
Compute the non-deterministic finite automaton (NFA) by using Thompson's algorithm. Compute the minimal deterministic finite automaton (DFA).
Indicate the number of processing steps for the abaabb 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.
Applying the determination algorithm to the above NFA, the following determination table is obtained:
| 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).