Theoretical Aspects of Lexical Analysis/Exercise 2 - Revision history

Root at 17:08, 6 August 2025

2025-08-06T17:08:05Z

← Older revision		Revision as of 17:08, 6 August 2025
Line 1:		Line 1:
	__NOTOC__		__NOTOC__
	~~<div class="section-container auto" data-section>~~
	~~<div class~~=~~"section">~~		== Problem ==
	~~<p class~~=~~"title" data-section-title>~~Problem~~</p>~~
	~~<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>~~		== Solution ==
	~~</div>~~
	~~<div class~~=~~"section">~~
	~~<p class~~=~~"title" data-section-title>~~Solution~~</p>~~
	~~<div class~~=~~"content" data-section-content>~~
	~~<!-- ====================== 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:
	<~~dot-hack~~>		<kroki lang="graphviz">
	digraph nfa {		digraph nfa {
	{ node [shape=circle style=invis] start }		{ node [shape=circle style=invis] start }
Line 36:		Line 30:
	fontsize=10		fontsize=10
	}		}
	</~~dot-hack~~>		</kroki>

	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:
Line 91:		Line 85:
	{\| 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 106:		Line 100:
	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 120:		Line 114:
	fontsize=10		fontsize=10
	}		}
	</~~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 132:		Line 126:
	fontsize=10		fontsize=10
	}		}
	</~~dot-hack~~>		</kroki>
	\|}		\|}
	~~<!-- ====================== END OF SOLUTION ====================== -->~~
	~~</div>~~
	~~</div>~~
	~~</div>~~

	[[category:Compiladores]]		[[category:Compiladores]]

Root at 20:39, 11 February 2019

2019-02-11T20:39:53Z

← Older revision		Revision as of 20:39, 11 February 2019
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:
	<~~graph~~>		<dot-hack>
	digraph nfa {		digraph nfa {
	{ node [shape=circle style=invis] start }		{ node [shape=circle style=invis] start }
Line 35:		Line 35:
	10 -> 1; 10 -> 11		10 -> 1; 10 -> 11
	fontsize=10		fontsize=10
	~~//label="NFA for (a\|b)*"~~
	}		}
	</~~graph~~>		</dot-hack>


	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:
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~~>		<dot-hack>
	digraph dfa {		digraph dfa {
	{ node [shape=circle style=invis] start }		{ node [shape=circle style=invis] start }
Line 107:		Line 105:
	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 122:		Line 119:
	012 -> 012 [label="b"]		012 -> 012 [label="b"]
	fontsize=10		fontsize=10
	~~//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 135:		Line 131:
	"{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"~~
	}		}
	</~~graph~~>		</dot-hack>
	\|}		\|}
	<!-- ====================== END OF SOLUTION ====================== -->		<!-- ====================== END OF SOLUTION ====================== -->

Root at 14:37, 6 April 2015

2015-04-06T14:37:47Z

← Older revision		Revision as of 14:37, 6 April 2015
Line 144:		Line 144:
	</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:35, 18 February 2015

2015-02-18T18:35:06Z

← Older revision		Revision as of 18:35, 18 February 2015
Line 1:		Line 1:
			__NOTOC__
			<div class="section-container auto" data-section>
			<div class="section">
			<p class="title" data-section-title>Problem</p>
			<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 ====================== -->
	== ~~NFA~~ ==		</div>
			</div>
	The ~~following is the result of~~ applying Thompson's algorithm.		<div class="section">
			<p class="title" data-section-title>Solution</p>
			<div class="content" data-section-content>
			<!-- ====================== 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:
	<graph>		<graph>
	digraph nfa {		digraph nfa {
Line 30:		Line 39:
	</graph>		</graph>

	~~== DFA ==~~

	~~Determination table for the above NFA:~~

			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 83:		Line 90:
	! style="font-weight: normal; align: center; background: #e6e6e6;" \| '''2'''		! style="font-weight: normal; align: center; background: #e6e6e6;" \| '''2'''
	\|}		\|}


	{\| 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 {
Line 134:		Line 139:
	</graph>		</graph>
	\|}		\|}
			<!-- ====================== END OF SOLUTION ====================== -->
			</div>
			</div>
			</div>

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

Root at 04:05, 22 March 2009

2009-03-22T04:05:21Z

← Older revision		Revision as of 04:05, 22 March 2009
Line 3:		Line 3:
	* <nowiki>(a\|b)*</nowiki>		* <nowiki>(a\|b)*</nowiki>

	~~== Solution ==~~		== NFA ==

	=== NFA ===

	The following is the result of applying Thompson's algorithm.		The following is the result of applying Thompson's algorithm.
Line 32:		Line 30:
	</graph>		</graph>

	=== DFA ===		== DFA ==

	Determination table for the above NFA:		Determination table for the above NFA:

Root: /* DFA */

2009-03-22T00:31:38Z

DFA

← Older revision		Revision as of 00:31, 22 March 2009
Line 129:		Line 129:
	node [shape=none,fixedsize=true,width=0.2,fontsize=10]		node [shape=none,fixedsize=true,width=0.2,fontsize=10]
	" {0, 1, 2}" -> "{}" [label="NF",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=" F",fontsize=10]
	"{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"

Root at 00:08, 22 March 2009

2009-03-22T00:08:54Z

@@ Line 4: / Line 4: @@
 == Solution ==
 [[category:Teaching]]
 [[category:Compilers]]
 [[en:Theoretical Aspects of Lexical Analysis]]

Root at 20:18, 21 March 2009

2009-03-21T20:18:12Z

← Older revision		Revision as of 20:18, 21 March 2009
Line 2:		Line 2:

	* <nowiki>(a\|b)*</nowiki>		* <nowiki>(a\|b)*</nowiki>

			== Solution ==

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

Root at 20:17, 21 March 2009

2009-03-21T20:17:37Z

← Older revision		Revision as of 20:17, 21 March 2009
Line 2:		Line 2:

	* <nowiki>(a\|b)*</nowiki>		* <nowiki>(a\|b)*</nowiki>

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

Root: New page: Use Thompson's algorithm to build the NFA for the following regular expression. Build the corresponding DFA and minimize it. * (a|b)*

2009-03-21T20:15:36Z

New page: Use Thompson's algorithm to build the NFA for the following regular expression. Build the corresponding DFA and minimize it. * <nowiki>(a*|b*)*</nowiki>

New page

Use Thompson's algorithm to build the NFA for the following regular expression. Build the corresponding DFA and minimize it.

* <nowiki>(a*|b*)*</nowiki>