Theoretical Aspects of Lexical Analysis/Exercise 3 - Revision history

Root at 18:24, 26 April 2026

2026-04-26T18:24:58Z

← Older revision		Revision as of 18:24, 26 April 2026
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:
	<~~dot-hack~~>		<kroki lang="graphviz">
	digraph nfa {		digraph nfa {
	{ node [shape=circle style=invis] start }		{ node [shape=circle style=invis] start }
Line 33:		Line 33:
	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 89:		Line 89:
	! 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 103:		Line 103:
	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 118:		Line 118:
	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.		! style="text-align: left; font-weight:normal; vertical-align: top; width: 50%;" \| The minimization tree is as follows.

	<~~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 130:		Line 130:
	fontsize=10		fontsize=10
	}		}
	</~~dot-hack~~>		</kroki>
	\|}		\|}
	<!-- ====================== END OF SOLUTION ====================== -->		<!-- ====================== END OF SOLUTION ====================== -->

Root at 20:42, 11 February 2019

2019-02-11T20:42:36Z

← Older revision		Revision as of 20:42, 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 32:		Line 32:
	7 -> 1; 7 -> 8		7 -> 1; 7 -> 8
	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 90:		Line 89:
	! 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 103:		Line 102:
	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 119:		Line 117:
	1 -> 02 [label="b"]		1 -> 02 [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.		! style="text-align: left; font-weight:normal; vertical-align: top; width: 50%;" \| The minimization tree is as follows.

	<~~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 132:		Line 129:
	"{0, 2}" -> "{0,2} " [label=" a,b",fontsize=10]		"{0, 2}" -> "{0,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:59Z

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

2015-02-18T18:38:11Z

← Older revision		Revision as of 18:38, 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 27:		Line 36:
	</graph>		</graph>

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

	~~Determination table for~~ the above NFA:

	{\| 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 130:		Line 136:
	</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: /* DFA */

2009-03-22T04:10:17Z

DFA

← Older revision		Revision as of 04:10, 22 March 2009
Line 117:		Line 117:
	</graph>		</graph>

	! 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.

	<graph>		<graph>

Root at 04:05, 22 March 2009

2009-03-22T04:05:56Z

← 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 29:		Line 27:
	</graph>		</graph>

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

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

Root at 00:31, 22 March 2009

2009-03-22T00:31:09Z

@@ 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:14Z

← 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:42Z

← 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:16:01Z

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>