Theoretical Aspects of Lexical Analysis/Exercise 5

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 '<div id="mynetwork2" style="height: 600px;"></div><script type="text/javascript">var container = document.getElementById("mynetwork2"); var nodes = [ {id: "s", label: "s", level: 0 }, {id: 0, label: "0", group: "all", level: 1}, {id: 1, label: "1", group: "ab*", level: 2}, {id: 2, label: "2", group: "ab*"}, {id: 3, label: "3final", level: 9, group: "ab*"}, {id: 4, label: "4", group: "ab*a", level: 2}, {id: 5, label: "5", group: "ab*a"}, {id: 6, label: "6", group: "ab*a"}, {id: 7, label: "7", group: "ab*a"}, {id: 8, label: "8final", level: 9, group: "ab*a"}, {id: 9, label: "9", group: "a|b", level: 2}, {id: 10, label: "10", group: "a|b"}, {id: 11, label: "11", group: "a|b"}, {id: 12, label: "12", group: "a|b"}, {id: 13, label: "13", group: "a|b"}, {id: 14, label: "14final", level: 9, group: "a|b"} ]; var edges = [ {from: "s", to: 0}, {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 = { nodes: { color: { background: "white", border: "#2B7CE9" }, shape: "circle", radius: 30 }, hierarchicalLayout: {layout: "direction", direction: directionInput.value } }; 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:

<graph> 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
 //label="DFA for (a|b)*abb(a|b)*"

} </graph>

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).