Theoretical Aspects of Lexical Analysis/Exercise 1 - Revision history

Root at 18:22, 26 April 2026

2026-04-26T18:22:27Z

← Older revision		Revision as of 18:22, 26 April 2026
Line 18:		Line 18:
	The non-deterministic finite automaton (NFA), built by applying Thompson's algorithm to the regular expression '''<nowiki>(a\|b)*</nowiki>''' is the following:		The non-deterministic finite automaton (NFA), built by applying Thompson's algorithm to the regular expression '''<nowiki>(a\|b)*</nowiki>''' is the following:
	{{CollapsedCode\|NFA for <nowiki>(a\|b)*</nowiki>\|		{{CollapsedCode\|NFA for <nowiki>(a\|b)*</nowiki>\|
	<~~dot-hack~~>		<kroki lang="graphviz">
	digraph nfa {		digraph nfa {
	{ node [shape=circle style=invis] start }		{ node [shape=circle style=invis] start }
Line 37:		Line 37:
	fontsize=10		fontsize=10
	}		}
	</~~dot-hack~~>		</kroki>
	}}		}}

Line 93:		Line 93:
	{\| width="100%"		{\| width="100%"
	! style="text-align: left; font-weight:normal; vertical-align: top; width: 50%;" \|Graphically, the DFA is represented as follows:		! style="text-align: left; font-weight:normal; vertical-align: top; width: 50%;" \|Graphically, the DFA is represented as follows:
	<~~dot-hack~~>		<kroki lang="graphviz">
	digraph dfa {		digraph dfa {
	{ node [shape=circle style=invis] start }		{ node [shape=circle style=invis] start }
Line 108:		Line 108:
	fontsize=10		fontsize=10
	}		}
	</~~dot-hack~~>		</kroki>

	Given the minimization tree to the right, the final minimal DFA is:		Given the minimization tree to the right, the final minimal DFA is:
	<~~dot-hack~~>		<kroki lang="graphviz">
	digraph dfamin {		digraph dfamin {
	{ node [shape=circle style=invis] start }		{ node [shape=circle style=invis] start }
Line 123:		Line 123:
	/label="DFA for (a\|b)"*/		/label="DFA for (a\|b)"*/
	}		}
	</~~dot-hack~~>		</kroki>

	! style="text-align: left; font-weight:normal; vertical-align: top; width: 50%;" \| The minimization tree is as follows. As can be seen, the states are indistinguishable.		! style="text-align: left; font-weight:normal; vertical-align: top; width: 50%;" \| The minimization tree is as follows. As can be seen, the states are indistinguishable.

	<~~dot-hack~~>		<kroki lang="graphviz">
	digraph mintree {		digraph mintree {
	node [shape=none,fixedsize=true,width=0.2,fontsize=10]		node [shape=none,fixedsize=true,width=0.2,fontsize=10]
Line 136:		Line 136:
	/label="Minimization tree"/		/label="Minimization tree"/
	}		}
	</~~dot-hack~~>		</kroki>
	\|}		\|}
	<!-- ====================== END OF SOLUTION ====================== -->		<!-- ====================== END OF SOLUTION ====================== -->

Root at 20:38, 11 February 2019

2019-02-11T20:38:01Z

← Older revision		Revision as of 20:38, 11 February 2019
Line 18:		Line 18:
	The non-deterministic finite automaton (NFA), built by applying Thompson's algorithm to the regular expression '''<nowiki>(a\|b)*</nowiki>''' is the following:		The non-deterministic finite automaton (NFA), built by applying Thompson's algorithm to the regular expression '''<nowiki>(a\|b)*</nowiki>''' is the following:
	{{CollapsedCode\|NFA for <nowiki>(a\|b)*</nowiki>\|		{{CollapsedCode\|NFA for <nowiki>(a\|b)*</nowiki>\|
	<~~graph~~>		<dot-hack>
	digraph nfa {		digraph nfa {
	{ node [shape=circle style=invis] start }		{ node [shape=circle style=invis] start }
Line 36:		Line 36:
	0 -> 7		0 -> 7
	fontsize=10		fontsize=10
	~~//label="NFA for (a\|b)*"~~
	}		}
	</~~graph~~>		</dot-hack>
	}}		}}

Line 94:		Line 93:
	{\| width="100%"		{\| width="100%"
	! style="text-align: left; font-weight:normal; vertical-align: top; width: 50%;" \|Graphically, the DFA is represented as follows:		! style="text-align: left; font-weight:normal; vertical-align: top; width: 50%;" \|Graphically, the DFA is represented as follows:
	<~~graph~~>		<dot-hack>
	digraph dfa {		digraph dfa {
	{ node [shape=circle style=invis] start }		{ node [shape=circle style=invis] start }
Line 108:		Line 107:
	2 -> 2 [label="b"]		2 -> 2 [label="b"]
	fontsize=10		fontsize=10
	~~//label="DFA for (a\|b)*"~~
	}		}
	</~~graph~~>		</dot-hack>

	Given the minimization tree to the right, the final minimal DFA is:		Given the minimization tree to the right, the final minimal DFA is:
	<~~graph~~>		<dot-hack>
	digraph dfamin {		digraph dfamin {
	{ node [shape=circle style=invis] start }		{ node [shape=circle style=invis] start }
Line 123:		Line 121:
	012 -> 012 [label="b"]		012 -> 012 [label="b"]
	fontsize=10		fontsize=10
	//label="DFA for (a\|b)*"		/label="DFA for (a\|b)"*/
	}		}
	</~~graph~~>		</dot-hack>

	! style="text-align: left; font-weight:normal; vertical-align: top; width: 50%;" \| The minimization tree is as follows. As can be seen, the states are indistinguishable.		! style="text-align: left; font-weight:normal; vertical-align: top; width: 50%;" \| The minimization tree is as follows. As can be seen, the states are indistinguishable.

	<~~graph~~>		<dot-hack>
	digraph mintree {		digraph mintree {
	node [shape=none,fixedsize=true,width=0.2,fontsize=10]		node [shape=none,fixedsize=true,width=0.2,fontsize=10]
Line 136:		Line 134:
	"{0, 1, 2}" -> "{0, 1, 2} " [label="a,b",fontsize=10]		"{0, 1, 2}" -> "{0, 1, 2} " [label="a,b",fontsize=10]
	fontsize=10		fontsize=10
	//label="Minimization tree"		/label="Minimization tree"/
	}		}
	</~~graph~~>		</dot-hack>
	\|}		\|}
	<!-- ====================== END OF SOLUTION ====================== -->		<!-- ====================== END OF SOLUTION ====================== -->
Line 144:		Line 142:
	</div>		</div>
	</div>		</div>

	~~<dot-hack>~~
	~~digraph mintree {~~
	~~node [shape=none,fixedsize=true,width=0.2,fontsize=10]~~
	~~" {0, 1, 2}" -> "{}" [label="NF",fontsize=10]~~
	~~" {0, 1, 2}" -> "{0, 1, 2}" [label="F",fontsize=10]~~
	~~"{0, 1, 2}" -> "{0, 1, 2} " [label="a,b",fontsize=10]~~
	~~fontsize=10~~
	~~/label="Minimization tree"/~~
	}
	~~</dot-hack>~~

	[[category:Compiladores]]		[[category:Compiladores]]
	[[category:Ensino]]		[[category:Ensino]]
	[[en:Theoretical Aspects of Lexical Analysis]]		[[en:Theoretical Aspects of Lexical Analysis]]

Root at 18:38, 11 February 2019

2019-02-11T18:38:55Z

← Older revision		Revision as of 18:38, 11 February 2019
Line 145:		Line 145:
	</div>		</div>

	<~~runphp~~>		<dot-hack>
	~~echo<<<___EOT___~~		digraph mintree {
	~~<script src~~=~~"/~david.matos/p/viz~~.~~js" type~~="~~application/javascript~~">~~</script>~~		node [shape=none,fixedsize=true,width=0.2,fontsize=10]
	~~<script src~~="~~/~david.matos/p/d3.v5.min.js~~" ~~type~~="~~application/javascript~~">~~</script>~~		" {0, 1, 2}" -> "{}" [label="NF",fontsize=10]
	~~<script type=~~"~~application/javascript~~">		" {0, 1, 2}" -> "{0, 1, 2}" [label="F",fontsize=10]
	~~d3.select(~~"~~#graph~~")		"{0, 1, 2}" -> "{0, 1, 2} " [label="a,b",fontsize=10]
	~~.graphviz()~~		fontsize=10
	~~.dot('digraph~~ {a -> b~~}')~~		/label="Minimization tree"/
	~~.render();~~		}
	</~~script>~~		</dot-hack>
	~~___EOT___;~~
	</~~runphp~~>

	[[category:Compiladores]]		[[category:Compiladores]]
	[[category:Ensino]]		[[category:Ensino]]
	[[en:Theoretical Aspects of Lexical Analysis]]		[[en:Theoretical Aspects of Lexical Analysis]]

Root at 14:17, 11 February 2019

2019-02-11T14:17:47Z

← Older revision		Revision as of 14:17, 11 February 2019
Line 147:		Line 147:
	<runphp>		<runphp>
	echo<<<___EOT___		echo<<<___EOT___
	<script src="/p/viz.js" type="application/javascript"></script>		<script src="/~david.matos/p/viz.js" type="application/javascript"></script>
	<script src="/p/d3.v5.min.js" type="application/javascript"></script>		<script src="/~david.matos/p/d3.v5.min.js" type="application/javascript"></script>
	<script type="application/javascript">		<script type="application/javascript">
	d3.select("#graph")		d3.select("#graph")

Root at 14:16, 11 February 2019

2019-02-11T14:16:14Z

← Older revision		Revision as of 14:16, 11 February 2019
Line 1:		Line 1:
	__NOTOC__		__NOTOC__

	<div class="section-container auto" data-section>		<div class="section-container auto" data-section>
	<div class="section">		<div class="section">
Line 143:		Line 144:
	</div>		</div>
	</div>		</div>

			<runphp>
			echo<<<___EOT___
			<script src="/p/viz.js" type="application/javascript"></script>
			<script src="/p/d3.v5.min.js" type="application/javascript"></script>
			<script type="application/javascript">
			d3.select("#graph")
			.graphviz()
			.dot('digraph {a -> b}')
			.render();
			</script>
			___EOT___;
			</runphp>

	[[category:Compiladores]]		[[category:Compiladores]]
	[[category:Ensino]]		[[category:Ensino]]
	[[en:Theoretical Aspects of Lexical Analysis]]		[[en:Theoretical Aspects of Lexical Analysis]]

Root at 18:35, 17 December 2015

2015-12-17T18:35:45Z

← Older revision		Revision as of 18:35, 17 December 2015
Line 16:		Line 16:
	<!-- ====================== START OF SOLUTION ====================== -->		<!-- ====================== START OF SOLUTION ====================== -->
	The non-deterministic finite automaton (NFA), built by applying Thompson's algorithm to the regular expression '''<nowiki>(a\|b)*</nowiki>''' is the following:		The non-deterministic finite automaton (NFA), built by applying Thompson's algorithm to the regular expression '''<nowiki>(a\|b)*</nowiki>''' is the following:
	{{CollapsedCode\|NFA for (a\|b)*\|		{{CollapsedCode\|NFA for <nowiki>(a\|b)*</nowiki>\|
	<graph>		<graph>
	digraph nfa {		digraph nfa {

Root at 18:35, 17 December 2015

2015-12-17T18:35:09Z

← Older revision		Revision as of 18:35, 17 December 2015
Line 16:		Line 16:
	<!-- ====================== START OF SOLUTION ====================== -->		<!-- ====================== START OF SOLUTION ====================== -->
	The non-deterministic finite automaton (NFA), built by applying Thompson's algorithm to the regular expression '''<nowiki>(a\|b)*</nowiki>''' is the following:		The non-deterministic finite automaton (NFA), built by applying Thompson's algorithm to the regular expression '''<nowiki>(a\|b)*</nowiki>''' is the following:
			{{CollapsedCode\|NFA for (a\|b)*\|
	<graph>		<graph>
	digraph nfa {		digraph nfa {
Line 37:		Line 38:
	}		}
	</graph>		</graph>
			}}

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

Root at 14:36, 6 April 2015

2015-04-06T14:36:16Z

← Older revision		Revision as of 14:36, 6 April 2015
Line 142:		Line 142:
	</div>		</div>

	[[category:~~Teaching~~]]		[[category:Compiladores]]
	[[category:~~Compilers~~]]		[[category:Ensino]]
	[[en:Theoretical Aspects of Lexical Analysis]]		[[en:Theoretical Aspects of Lexical Analysis]]

Root at 18:28, 18 February 2015

2015-02-18T18:28:22Z

← Older revision		Revision as of 18:28, 18 February 2015
Line 4:		Line 4:
	<p class="title" data-section-title>Problem</p>		<p class="title" data-section-title>Problem</p>
	<div class="content" data-section-content>		<div class="content" data-section-content>
			<!-- ====================== START OF PROBLEM ====================== -->
	Use Thompson's algorithm to build the NFA for the following regular expression. Build the corresponding DFA and minimize it.		Use Thompson's algorithm to build the NFA for the following regular expression. Build the corresponding DFA and minimize it.

	* '''<nowiki>(a\|b)*</nowiki>'''		* '''<nowiki>(a\|b)*</nowiki>'''
			<!-- ====================== END OF PROBLEM ====================== -->
	</div>		</div>
	</div>		</div>
Line 12:		Line 14:
	<p class="title" data-section-title>Solution</p>		<p class="title" data-section-title>Solution</p>
	<div class="content" data-section-content>		<div class="content" data-section-content>

	<!-- ====================== START OF SOLUTION ====================== -->		<!-- ====================== START OF SOLUTION ====================== -->

	The non-deterministic finite automaton (NFA), built by applying Thompson's algorithm to the regular expression '''<nowiki>(a\|b)*</nowiki>''' is the following:		The non-deterministic finite automaton (NFA), built by applying Thompson's algorithm to the regular expression '''<nowiki>(a\|b)*</nowiki>''' is the following:

	<graph>		<graph>
	digraph nfa {		digraph nfa {
Line 40:		Line 39:

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

	{\| cellspacing="2"		{\| cellspacing="2"
	! style="padding-left: 20px; padding-right: 20px; background: wheat;" \| I<sub>n</sub>		! style="padding-left: 20px; padding-right: 20px; background: wheat;" \| I<sub>n</sub>
Line 93:		Line 91:
	{\| width="100%"		{\| width="100%"
	! style="text-align: left; font-weight:normal; vertical-align: top; width: 50%;" \|Graphically, the DFA is represented as follows:		! style="text-align: left; font-weight:normal; vertical-align: top; width: 50%;" \|Graphically, the DFA is represented as follows:

	<graph>		<graph>
	digraph dfa {		digraph dfa {

Root at 18:13, 18 February 2015

2015-02-18T18:13:54Z

← Older revision		Revision as of 18:13, 18 February 2015
Line 141:		Line 141:
	\|}		\|}
	<!-- ====================== END OF SOLUTION ====================== -->		<!-- ====================== END OF SOLUTION ====================== -->
	~~</div>~~
	~~</div>~~
	~~<div class="section">~~
	~~<p class="title" data-section-title>Urna</p>~~
	~~<div class="content" data-section-content>~~
	3
	~~</div>~~
	~~</div>~~
	~~<div class="section">~~
	~~<p class="title" data-section-title>Magna</p>~~
	~~<div class="content" data-section-content>~~
	4
	</div>		</div>
	</div>		</div>
	</div>		</div>


	[[category:Teaching]]		[[category:Teaching]]
	[[category:Compilers]]		[[category:Compilers]]
	[[en:Theoretical Aspects of Lexical Analysis]]		[[en:Theoretical Aspects of Lexical Analysis]]