Difference between revisions of "Theoretical Aspects of Lexical Analysis/Exercise 5"

Revision as of 18:59, 27 January 2015

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.

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.

DFA

Determination table for the above NFA:

I_n	α∈Σ	move(I_n, α)	ε-closure(move(I_n, α))	I_n+1 = ε-closure(move(I_n, α))
-	-	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).

Input Analysis

I_n	Input	I_n+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).

@@ Line 39: / Line 39: @@
 }
 </graph>
-== 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="mynetwork" style="height: 600px;"></div><script type="text/javascript">var container = document.getElementById("mynetwork"); var options = { hierarchicalLayout: { layout: "direction", direction: "LR" }  }; var data = { dot: \'digraph {  { node [shape=circle,style=invis] s };  { node [shape=doublecircle] 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 ==