Theoretical Aspects of Lexical Analysis/Exercise 4 - Revision history

Root at 18:36, 26 April 2026

2026-04-26T18:36:45Z

Root at 18:26, 26 April 2026

2026-04-26T18:26:56Z

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

Line 205:		Line 205:

	{{CollapsedCode\|DFA\|		{{CollapsedCode\|DFA\|
	<~~dot-hack~~>		<kroki lang="graphviz">
	digraph dfa {		digraph dfa {
	{ node [shape=circle style=invis] s }		{ node [shape=circle style=invis] s }
Line 232:		Line 232:
	fontsize=10		fontsize=10
	}		}
	</~~dot-hack~~>		</kroki>
	}}		}}
	The minimization tree is as follows:		The minimization tree is as follows:
Line 245:		Line 245:

	{{CollapsedCode\|Minimal DFA\|		{{CollapsedCode\|Minimal DFA\|
	<~~dot-hack~~>		<kroki lang="graphviz">
	digraph dfamin {		digraph dfamin {
	{ node [shape=circle style=invis] s }		{ node [shape=circle style=invis] s }
Line 262:		Line 262:
	fontsize=10		fontsize=10
	}		}
	</~~dot-hack~~>		</kroki>
	}}		}}

Root at 20:44, 11 February 2019

2019-02-11T20:44:36Z

← Older revision		Revision as of 20:44, 11 February 2019
Line 10:		Line 10:
	The non-deterministic finite automaton (NFA), built by applying Thompson's algorithm to the regular expression '''<nowiki>(a\|b)abb(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)abb(a\|b)</nowiki>''' is the following:
	{{CollapsedCode\|NFA\|		{{CollapsedCode\|NFA\|
	<~~graph~~>		<dot-hack>
	digraph nfa {		digraph nfa {
	{ node [shape=circle style=invis] s }		{ node [shape=circle style=invis] s }
Line 45:		Line 45:

	fontsize=10		fontsize=10
	~~//label="NFA for (a\|b)abb(a\|b)"~~
	}		}
	</~~graph~~>		</dot-hack>
	}}		}}

Line 206:		Line 205:

	{{CollapsedCode\|DFA\|		{{CollapsedCode\|DFA\|
	<~~graph~~>		<dot-hack>
	digraph dfa {		digraph dfa {
	{ node [shape=circle style=invis] s }		{ node [shape=circle style=invis] s }
Line 232:		Line 231:
	8 -> 6 [label="b",fontsize=10]		8 -> 6 [label="b",fontsize=10]
	fontsize=10		fontsize=10
	~~//label="DFA for (a\|b)abb(a\|b)"~~
	}		}
	</~~graph~~>		</dot-hack>
	}}		}}
	The minimization tree is as follows:		The minimization tree is as follows:
Line 247:		Line 245:

	{{CollapsedCode\|Minimal DFA\|		{{CollapsedCode\|Minimal DFA\|
	<~~graph~~>		<dot-hack>
	digraph dfamin {		digraph dfamin {
	{ node [shape=circle style=invis] s }		{ node [shape=circle style=invis] s }
Line 263:		Line 261:
	45678 -> 45678 [label="b",fontsize=10]		45678 -> 45678 [label="b",fontsize=10]
	fontsize=10		fontsize=10
	~~//label="DFA for (a\|b)abb(a\|b)"~~
	}		}
	</~~graph~~>		</dot-hack>
	}}		}}

Root: /* Solution */

2016-06-24T08:04:30Z

Solution

Show changes

Root: /* Solution */

2016-06-24T07:58:11Z

Solution

Show changes

Root at 07:53, 24 June 2016

2016-06-24T07:53:19Z

← Older revision		Revision as of 07:53, 24 June 2016
Line 1:		Line 1:
	{{TOCright}}		{{TOCright}}

	==Problem??		==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.

Line 212:		Line 212:

	{{CollapsedCode\|Minimization tree\|		{{CollapsedCode\|Minimization tree\|
	[[image:aula3p4mintree.jpg\|~~200~~]]		[[image:aula3p4mintree.jpg\|350px]]
	}}		}}

	The tree expansion for non-splitting sets has been omitted for simplicity ("a" transition for non-final states and the {0, 2} "a" and "b" transitions. The final states are all indistinguishable, regarding both "a" or "b" transitions (remember that, at this stage, we assume that individual states -- i.e., the final states -- are all indistinguishable).		<!--The tree expansion for non-splitting sets has been omitted for simplicity ("a" transition for non-final states and the {0, 2} "a" and "b" transitions. The final states are all indistinguishable, regarding both "a" or "b" transitions (remember that, at this stage, we assume that individual states -- i.e., the final states -- are all indistinguishable).
			-->
	Given the minimization tree above, the final minimal DFA is as follows:		Given the minimization tree above, the final minimal DFA is as follows:

Root at 07:51, 24 June 2016

2016-06-24T07:51:33Z

← Older revision		Revision as of 07:51, 24 June 2016
Line 1:		Line 1:
	~~__NOTOC__~~		{{TOCright}}
	~~<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)abb(a\|b)</nowiki>'''		* '''<nowiki>(a\|b)abb(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)abb(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)abb(a\|b)</nowiki>''' is the following:
			{{CollapsedCode\|NFA\|
	<graph>		<graph>
	digraph nfa {		digraph nfa {
Line 54:		Line 48:
	}		}
	</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:

			{{CollapsedCode\|Determination table\|
	{\| 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 178:		Line 174:
	! style="font-weight: normal; align: center; background: #e6e6e6;" \| '''6'''		! style="font-weight: normal; align: center; background: #e6e6e6;" \| '''6'''
	\|}		\|}
			}}

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

			{{CollapsedCode\|DFA\|
	<graph>		<graph>
	digraph dfa {		digraph dfa {
Line 210:		Line 208:
	}		}
	</graph>		</graph>
			}}
	The minimization tree is as follows:		The minimization tree is as follows:

	[[image:aula3p4mintree.jpg]]		{{CollapsedCode\|Minimization tree\|
			[[image:aula3p4mintree.jpg\|200]]
			}}

	The tree expansion for non-splitting sets has been omitted for simplicity ("a" transition for non-final states and the {0, 2} "a" and "b" transitions. The final states are all indistinguishable, regarding both "a" or "b" transitions (remember that, at this stage, we assume that individual states -- i.e., the final states -- are all indistinguishable).		The tree expansion for non-splitting sets has been omitted for simplicity ("a" transition for non-final states and the {0, 2} "a" and "b" transitions. The final states are all indistinguishable, regarding both "a" or "b" transitions (remember that, at this stage, we assume that individual states -- i.e., the final states -- are all indistinguishable).
Line 219:		Line 219:
	Given the minimization tree above, the final minimal DFA is as follows:		Given the minimization tree above, the final minimal DFA is as follows:

			{{CollapsedCode\|Minimal DFA\|
	<graph>		<graph>
	digraph dfamin {		digraph dfamin {
Line 238:		Line 239:
	}		}
	</graph>		</graph>
	~~<!-- ====================== END OF SOLUTION ====================== -->~~		}}
	~~</div>~~
	~~</div>~~
	~~</div>~~

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

Root at 07:43, 24 June 2016

2016-06-24T07:43:56Z

@@ Line 213: / Line 213: @@
 The minimization tree is as follows:
-<graph>
+[[image:aula3p4mintree.jpg]]
 The tree expansion for non-splitting sets has been omitted for simplicity ("a" transition for non-final states and the {0, 2} "a" and "b" transitions. The final states are all indistinguishable, regarding both "a" or "b" transitions (remember that, at this stage, we assume that individual states -- i.e., the final states -- are all indistinguishable).

Root at 14:38, 6 April 2015

2015-04-06T14:38:17Z

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

2015-02-18T18:42:06Z

← Older revision		Revision as of 18:42, 18 February 2015
Line 56:		Line 56:

	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 179:		Line 180:

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

	<graph>		<graph>
	digraph dfa {		digraph dfa {
Line 209:		Line 211:
	</graph>		</graph>

	The minimization tree is as follows.		The minimization tree is as follows:

	<graph>		<graph>
	digraph mintree {		digraph mintree {
Line 226:		Line 229:
	The tree expansion for non-splitting sets has been omitted for simplicity ("a" transition for non-final states and the {0, 2} "a" and "b" transitions. The final states are all indistinguishable, regarding both "a" or "b" transitions (remember that, at this stage, we assume that individual states -- i.e., the final states -- are all indistinguishable).		The tree expansion for non-splitting sets has been omitted for simplicity ("a" transition for non-final states and the {0, 2} "a" and "b" transitions. The final states are all indistinguishable, regarding both "a" or "b" transitions (remember that, at this stage, we assume that individual states -- i.e., the final states -- are all indistinguishable).

	Given the minimization tree above, the final minimal DFA is: <graph>		Given the minimization tree above, the final minimal DFA is as follows:

			<graph>
	digraph dfamin {		digraph dfamin {
	{ node [shape=circle style=invis] s }		{ node [shape=circle style=invis] s }