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

Latest revision as of 18:39, 26 April 2026

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.

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

Applying the determination algorithm to the above NFA, the following determination table is obtained:

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 1: / Line 1: @@
 __NOTOC__
-<div class="section-container auto" data-section>
+Consider the lexical analyzer '''<nowiki>G = { ab, ab*, a|b }</nowiki>''', defined for the alphabet '''Σ = { a, b }'''.
-  <div class="section">
-    <p class="title" data-section-title>Problem</p>
+Compute the non-deterministic finite automaton (NFA) by using Thompson's algorithm. Compute the minimal deterministic finite automaton (DFA).
-    <div class="content" data-section-content>
-<!-- ====================== START OF PROBLEM ====================== -->
+Indicate the number of processing steps for the '''abaabb''' input string.
-Compute the non-deterministic finite automaton (NFA) by using Thompson's algorithm. Compute the minimal deterministic finite automaton (DFA).<br/>The alphabet is Σ = { a, b }. Indicate the number of processing steps for the given input string.
-* <nowiki>G = { ab, ab*, a|b }</nowiki>, input string = abaabb
+== NFA ==
-<!-- ====================== END OF PROBLEM ====================== -->
-    </div>
-  </div>
-  <div class="section">
-    <p class="title" data-section-title>Solution</p>
-    <div class="content" data-section-content>
-<!-- ====================== START OF SOLUTION ====================== -->
-Compute the non-deterministic finite automaton (NFA) by using Thompson's algorithm. Compute the minimal deterministic finite automaton (DFA).<br/>The alphabet is Σ = { a, b }. Indicate the number of processing steps for the given input string.
-* <nowiki>G = { ab, ab*, a|b }</nowiki>, input string = abaabb
 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>
+<kroki lang="graphviz">
-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>';
+digraph nfa {
-</runphp>
+     { 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
+-> 1
+-> 2 [label="a",fontsize=10]
+-> 3 [label="b",fontsize=10]
+-> 4
+-> 5 [label="a",fontsize=10]
+-> 6
+-> 8
+-> 7 [label="b",fontsize=10]
+-> 6
+-> 8
+-> 9
+-> 10
+-> 12
+-> 11 [label="a",fontsize=10]
+-> 13 [label="b",fontsize=10]
+-> 14
+-> 14
+   fontsize=10
+}
+</kroki>
+== DFA ==
 Applying the determination algorithm to the above NFA, the following determination table is obtained:
@@ Line 31: / Line 53: @@
 ! 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;" | 0
 ! style="font-weight: normal; align: left;   background: #ffffcc;" | 0, 1, 4, 9, 10, 12
@@ Line 38: / Line 60: @@
 |-
 ! 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;" | 2, 5, 11
 ! style="font-weight: normal; align: left;   background: #e6e6e6;" | 2, 5, 6, '''8''', 11, '''14'''
@@ Line 44: / Line 66: @@
 |-
 ! 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;" | 13
 ! style="font-weight: normal; align: left;   background: #e6e6e6;" | 13, '''14'''
@@ Line 50: / Line 72: @@
 |-
 ! 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;" | -
 ! style="font-weight: normal; align: left;   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;" | b
 ! style="font-weight: normal; align: center; background: #ffffcc;" | '''3''', 7
 ! style="font-weight: normal; align: left;   background: #ffffcc;" | '''3''', 6, 7, '''8'''
@@ Line 68: / Line 90: @@
 |-
 ! 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;" | -
 ! style="font-weight: normal; align: left;   background: #e6e6e6;" | -
@@ Line 80: / Line 102: @@
 |-
 ! 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;" | 7
 ! style="font-weight: normal; align: left;   background: #ffffcc;" | 6, 7, '''8'''
@@ Line 92: / Line 114: @@
 |-
 ! 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;" | 7
 ! style="font-weight: normal; align: left;   background: #e6e6e6;" | 6, 7, '''8'''
@@ Line 99: / Line 121: @@
 Graphically, the DFA is represented as follows:
+<kroki lang="graphviz">
-<runphp>
+digraph dfa {
-echo '<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>';
+     { node [shape=circle style=invis] s }
-</runphp>
+  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
+-> 1 [label="a",fontsize=10]
+-> 2 [label="b",fontsize=10]
+-> 3 [label="b",fontsize=10]
+-> 4 [label="b",fontsize=10]
+-> 4 [label="b",fontsize=10]
+  fontsize=10
+}
+</kroki>
 The minimization tree is as follows. Note that before considering transition behavior, states are split according to the token they recognize.
-<graph>
+<kroki lang="graphviz">
 digraph mintree {
    node [shape=none,fixedsize=true,width=0.3,fontsize=10]
    "{0, 1, 2, 3, 4}" -> "{0}" [label="NF",fontsize=10]
@@ Line 114: / Line 147: @@
    "{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}" -> "{1}" /*[label="  T3",fontsize=10]*/
    "{1, 4}" -> "{4}" [label="  b",fontsize=10]
    fontsize=10
-  //label="Minimization tree"
 }
-</graph>
+</kroki>
 The tree expansion for non-splitting sets has been omitted for simplicity ("a" transition for final states {1, 4}).
@@ Line 133: / Line 165: @@
 |-
 ! 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; 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; 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; align: center; background: #ffffcc;" | '''T1'''
 |-
@@ Line 170: / Line 202: @@
 The input string ''abaabb'' is, after 9 steps, split into three tokens: '''T1''' (corresponding to lexeme ''ab''), '''T2''' (''a''), and '''T2''' (''abb'').
-<!-- ====================== END OF SOLUTION ====================== -->
-    </div>
-  </div>
-</div>
-[[category:Teaching]]
+[[category:Compiladores]]
-[[category:Compilers]]
+[[category:Ensino]]
 [[en:Theoretical Aspects of Lexical Analysis]]

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

From Wiki**3

< Theoretical Aspects of Lexical Analysis

Latest revision as of 18:39, 26 April 2026

NFA

DFA

Input Analysis