Theoretical Aspects of Lexical Analysis/Exercise 5 - Revision history

Root at 18:39, 26 April 2026

2026-04-26T18:39:04Z

← Older revision		Revision as of 18:39, 26 April 2026
Line 10:		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~~>		<kroki lang="graphviz">
	digraph nfa {		digraph nfa {
	{ node [shape=circle style=invis] s }		{ node [shape=circle style=invis] s }
Line 40:		Line 40:
	fontsize=10		fontsize=10
	}		}
	</~~dot-hack>~~		</kroki>
	~~<!--~~
	~~<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>~~
	-->

	== DFA ==		== DFA ==
Line 126:		Line 121:

	Graphically, the DFA is represented as follows:		Graphically, the DFA is represented as follows:
	<~~dot-hack~~>		<kroki lang="graphviz">
	digraph dfa {		digraph dfa {
	{ node [shape=circle style=invis] s }		{ node [shape=circle style=invis] s }
Line 140:		Line 135:
	fontsize=10		fontsize=10
	}		}
	</~~dot-hack~~>		</kroki>
	~~<!--~~
	~~<runphp>~~
	~~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>~~
	~~-->~~
	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~~>		<kroki lang="graphviz">
	digraph mintree {		digraph mintree {
	node [shape=none,fixedsize=true,width=0.3,fontsize=10]		node [shape=none,fixedsize=true,width=0.3,fontsize=10]
Line 169:		Line 151:
	fontsize=10		fontsize=10
	}		}
	</~~dot-hack~~>		</kroki>

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

Root at 20:58, 11 February 2019

2019-02-11T20:58:42Z

← Older revision		Revision as of 20:58, 11 February 2019
Line 165:		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}" //[label=" T3",fontsize=10]		"{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

Root at 20:54, 11 February 2019

2019-02-11T20:54:28Z

← Older revision		Revision as of 20:54, 11 February 2019
Line 157:		Line 157:
	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.

	<~~graph~~>		<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]
Line 168:		Line 168:
	"{1, 4}" -> "{4}" [label=" b",fontsize=10]		"{1, 4}" -> "{4}" [label=" b",fontsize=10]
	fontsize=10		fontsize=10
	~~//label="Minimization tree"~~
	}		}
	</~~graph~~>		</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}).

Root at 20:53, 11 February 2019

2019-02-11T20:53:34Z

@@ Line 126: / Line 126: @@
 Graphically, the DFA is represented as follows:
 <runphp>
 echo<<<___EOT___
@@ Line 138: / Line 154: @@
 ___EOT___;
 </runphp>
+-->
 The minimization tree is as follows. Note that before considering transition behavior, states are split according to the token they recognize.

Root: /* NFA */

2019-02-11T20:51:50Z

NFA

@@ Line 10: / 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'''.
 <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>
 == DFA ==

Root at 14:38, 6 April 2015

2015-04-06T14:38:29Z

← Older revision		Revision as of 14:38, 6 April 2015
Line 173:		Line 173:
	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:~~Teaching~~]]		[[category:Compiladores]]
	[[category:~~Compilers~~]]		[[category:Ensino]]

	[[en:Theoretical Aspects of Lexical Analysis]]		[[en:Theoretical Aspects of Lexical Analysis]]

Root: /* DFA */

2015-03-02T16:03:58Z

DFA

← Older revision		Revision as of 16:03, 2 March 2015
Line 96:		Line 96:
	echo<<<___EOT___		echo<<<___EOT___
	<nowiki><div id="mydfa" style="height: 250px; width: 100%;"></div>		<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>		<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___;		___EOT___;
	</runphp>		</runphp>

Root: /* DFA */

2015-03-02T16:03:19Z

DFA

← Older revision		Revision as of 16:03, 2 March 2015
Line 93:		Line 93:

	Graphically, the DFA is represented as follows:		Graphically, the DFA is represented as follows:

	<runphp>		<runphp>
	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>';		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>

Root at 19:09, 18 February 2015

2015-02-18T19:09:53Z

Show changes

Root at 18:58, 18 February 2015

2015-02-18T18:58:13Z

← Older revision		Revision as of 18:58, 18 February 2015
Line 5:		Line 5:
	<div class="content" data-section-content>		<div class="content" data-section-content>
	<!-- ====================== START OF PROBLEM ====================== -->		<!-- ====================== START OF PROBLEM ====================== -->
	Consider the lexical analyzer '''<nowiki>G = { ab, ab*, a\|b }</nowiki>''', defined for the alphabet is '''Σ = { a, b }'''.		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).		Compute the non-deterministic finite automaton (NFA) by using Thompson's algorithm. Compute the minimal deterministic finite automaton (DFA).
Line 17:		Line 17:
	<div class="content" data-section-content>		<div class="content" data-section-content>
	<!-- ====================== START OF SOLUTION ====================== -->		<!-- ====================== START OF SOLUTION ====================== -->
	Consider the lexical analyzer '''<nowiki>G = { ab, ab*, a\|b }</nowiki>''', defined for the alphabet is '''Σ = { a, b }'''.		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).		Compute the non-deterministic finite automaton (NFA) by using Thompson's algorithm. Compute the minimal deterministic finite automaton (DFA).