Theoretical Aspects of Lexical Analysis/Exercise 5
From Wiki**3
< Theoretical Aspects of Lexical 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.
- G = { ab, ab*, a|b }, input string = abaabb
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 '
<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", } }, t2: { color: { border: "#f31d22", background: "#fa8a8c", } }, t3: { color: { border: "#ffa500", background: "#ffff00", } } }, edges: { style: "arrow" }, nodes: { color: { background: "white", border: "#2B7CE9", highlight: { background: "white", border: "#2B7CE9" } }, radius: 30 }, hierarchicalLayout: { direction: "LR" } }; var data = { nodes: nodes, edges: edges }; var network = new vis.Network(container, data, options);</script>';
</runphp>
DFA
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:
<runphp> echo '<div id="mydfa" style="height: 300px; 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" } }; var data = { nodes: nodes, edges: edges }; var network = new vis.Network(container, data, options);</script>'; </runphp>
The minimization tree is as follows. Note that before considering transition behavior, states are split according to the token they recognize.
<graph> digraph mintree {
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}" -> "{1, 2, 3, 4}" [label=" F",fontsize=10]
"{1, 2, 3, 4}" -> "{3}" [label=" T1",fontsize=10]
"{1, 2, 3, 4}" -> "{1, 4}" [label=" T2",fontsize=10]
"{1, 2, 3, 4}" -> "{2}" [label=" T3",fontsize=10]
"{1, 4}" -> "{1}" //[label=" T3",fontsize=10]
"{1, 4}" -> "{4}" [label=" b",fontsize=10]
fontsize=10
//label="Minimization tree"
} </graph>
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).
Input Analysis
| 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).