Theoretical Aspects of Lexical Analysis/Exercise 6 - Revision history

Root at 18:40, 26 April 2026

2026-04-26T18:40:44Z

← Older revision		Revision as of 18:40, 26 April 2026
Line 9:		Line 9:
	State '''3''' recognizes the first expression (token '''T1'''); state '''8''' recognizes token '''T2'''; and state '''14''' recognizes token '''T3'''.		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 37:		Line 37:
	fontsize=10		fontsize=10
	}		}
	</~~dot-hack~~>		</kroki>
	}}		}}

Line 132:		Line 132:

	{{CollapsedCode\|Graphical representation of the DFA\|		{{CollapsedCode\|Graphical representation of the DFA\|
	<~~dot-hack~~>		<kroki lang="graphviz">
	digraph dfa {		digraph dfa {
	{ node [shape=circle style=invis] s }		{ node [shape=circle style=invis] s }
Line 146:		Line 146:
	fontsize=10		fontsize=10
	}		}
	</~~dot-hack~~>		</kroki>
	}}		}}

Line 152:		Line 152:
	Note that before considering transition behavior, states are split according to the token they recognize.		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 166:		Line 166:
	fontsize=10		fontsize=10
	}		}
	</~~dot-hack~~>		</kroki>

	The tree expansion for sets {0, 4} and {1, 2} was only tested for "a" (sufficient).		The tree expansion for sets {0, 4} and {1, 2} was only tested for "a" (sufficient).

Root: /* DFA */

2019-02-12T10:14:32Z

DFA

← Older revision		Revision as of 10:14, 12 February 2019
Line 160:		Line 160:
	"{1, 2, 3, 5}" -> "{5}" [label=" T2",fontsize=10]		"{1, 2, 3, 5}" -> "{5}" [label=" T2",fontsize=10]
	"{1, 2, 3, 5}" -> "{1, 2}" [label=" T3",fontsize=10]		"{1, 2, 3, 5}" -> "{1, 2}" [label=" T3",fontsize=10]
	"{0, 4}" -> "{0}" //[label=" T3",fontsize=10]		"{0, 4}" -> "{0}" /[label=" T3",fontsize=10]/
	"{0, 4}" -> "{4}" [label=" a",fontsize=10]		"{0, 4}" -> "{4}" [label=" a",fontsize=10]
	"{1, 2}" -> "{1}" //[label=" T3",fontsize=10]		"{1, 2}" -> "{1}" /[label=" T3",fontsize=10]/
	"{1, 2}" -> "{2}" [label=" a",fontsize=10]		"{1, 2}" -> "{2}" [label=" a",fontsize=10]
	fontsize=10		fontsize=10

Root: /* DFA */

2019-02-12T10:13:49Z

DFA

← Older revision		Revision as of 10:13, 12 February 2019
Line 132:		Line 132:

	{{CollapsedCode\|Graphical representation of the DFA\|		{{CollapsedCode\|Graphical representation of the DFA\|
	<~~graph~~>		<dot-hack>
	digraph dfa {		digraph dfa {
	{ node [shape=circle style=invis] s }		{ node [shape=circle style=invis] s }
Line 145:		Line 145:
	4 -> 5 [label="a",fontsize=10]		4 -> 5 [label="a",fontsize=10]
	fontsize=10		fontsize=10
	~~//label="DFA for (a\|b)abb(a\|b)"~~
	}		}
	</~~graph~~>		</dot-hack>
	}}		}}

Line 153:		Line 152:
	Note that before considering transition behavior, states are split according to the token they recognize.		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 166:		Line 165:
	"{1, 2}" -> "{2}" [label=" a",fontsize=10]		"{1, 2}" -> "{2}" [label=" a",fontsize=10]
	fontsize=10		fontsize=10
	~~//label="Minimization tree"~~
	}		}
	</~~graph~~>		</dot-hack>

	The tree expansion for sets {0, 4} and {1, 2} was only tested for "a" (sufficient).		The tree expansion for sets {0, 4} and {1, 2} was only tested for "a" (sufficient).

Root: /* NFA */

2019-02-12T10:13:22Z

NFA

← Older revision		Revision as of 10:13, 12 February 2019
Line 9:		Line 9:
	State '''3''' recognizes the first expression (token '''T1'''); state '''8''' recognizes token '''T2'''; and state '''14''' recognizes token '''T3'''.		State '''3''' recognizes the first expression (token '''T1'''); state '''8''' recognizes token '''T2'''; and state '''14''' recognizes token '''T3'''.

	<~~graph~~>		<dot-hack>
	digraph nfa {		digraph nfa {
	{ node [shape=circle style=invis] s }		{ node [shape=circle style=invis] s }
Line 36:		Line 36:
	13 -> 14		13 -> 14
	fontsize=10		fontsize=10
	~~//label="NFA for (a\|b)abb(a\|b)"~~
	}		}
	</~~graph~~>		</dot-hack>
	}}		}}

Root: /* DFA */

2016-03-05T10:36:38Z

DFA

← Older revision		Revision as of 10:36, 5 March 2016
Line 43:		Line 43:
	== DFA ==		== DFA ==

	~~{{CollapsedCode\|~~Determination table for the above NFA\|		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 131:
	\|-		\|-
	\|}		\|}
	}}

	{{CollapsedCode\|Graphical representation of the DFA\|		{{CollapsedCode\|Graphical representation of the DFA\|

Root: /* DFA */

2016-03-05T10:34:19Z

DFA

← Older revision		Revision as of 10:34, 5 March 2016
Line 43:		Line 43:
	== DFA ==		== DFA ==

	Determination table for the above NFA:		{{CollapsedCode\|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 131:		Line 130:
	\|-		\|-
	\|}		\|}
			}}

	~~Graphically,~~ the DFA ~~is represented as follows:~~		{{CollapsedCode\|Graphical representation of the DFA\|

	<graph>		<graph>
	digraph dfa {		digraph dfa {
Line 150:		Line 149:
	}		}
	</graph>		</graph>
			}}

	~~The~~ minimization tree ~~is as follows.~~ Note that before considering transition behavior, states are split according to the token they recognize.		{{CollapsedCode\|DFA minimization tree\|
			Note that before considering transition behavior, states are split according to the token they recognize.

	<graph>		<graph>
Line 173:		Line 174:

	Given the minimization tree, the final minimal DFA is exactly the same as the original DFA (all leaf sets are singular).		Given the minimization tree, the final minimal DFA is exactly the same as the original DFA (all leaf sets are singular).
			}}

	== Input Analysis ==		== Input Analysis ==

Root: /* NFA */

2016-03-05T10:32:43Z

NFA

← Older revision		Revision as of 10:32, 5 March 2016
Line 5:		Line 5:
	== NFA ==		== NFA ==

	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.
			{{CollapsedCode\|NFA built by Thompson's algorithm\|
			State '''3''' recognizes the first expression (token '''T1'''); state '''8''' recognizes token '''T2'''; and state '''14''' recognizes token '''T3'''.

	<graph>		<graph>
Line 37:		Line 39:
	}		}
	</graph>		</graph>
			}}

	== DFA ==		== DFA ==

Root at 14:38, 6 April 2015

2015-04-06T14:38:50Z

← Older revision		Revision as of 14:38, 6 April 2015
Line 245:		Line 245:
	The input string ''aaabaaaaa'' is, after 16 steps, split into three tokens: '''T1''' (corresponding to lexeme ''aa''), '''T3''' (''a''), '''T3''' (''b''), '''T2''' (''aaaa''), and '''T3''' (''a'').		The input string ''aaabaaaaa'' is, after 16 steps, split into three tokens: '''T1''' (corresponding to lexeme ''aa''), '''T3''' (''a''), '''T3''' (''b''), '''T2''' (''aaaa''), and '''T3''' (''a'').

	[[category:~~Teaching~~]]		[[category:Compiladores]]
	[[category:~~Compilers~~]]		[[category:Ensino]]

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

Root at 17:40, 28 March 2009

2009-03-28T17:40:48Z

← Older revision		Revision as of 17:40, 28 March 2009
Line 243:		Line 243:
	\|}		\|}

	~~<!--~~		The input string ''aaabaaaaa'' is, after 16 steps, split into three tokens: '''T1''' (corresponding to lexeme ''aa''), '''T3''' (''a''), '''T3''' (''b''), '''T2''' (''aaaa''), and '''T3''' (''a'').
	The input string ''aaabaaaaa'' is, after 9 steps, split into three tokens: '''T1''' (corresponding to lexeme ''ab''), '''T2''' (''a''), and '''T2''' (''~~abb~~'').
	~~-->~~
	[[category:Teaching]]		[[category:Teaching]]
	[[category:Compilers]]		[[category:Compilers]]
	[[en:Theoretical Aspects of Lexical Analysis]]		[[en:Theoretical Aspects of Lexical Analysis]]

Root at 18:17, 22 March 2009

2009-03-22T18:17:01Z

← Older revision		Revision as of 18:17, 22 March 2009
Line 180:		Line 180:
	! style="font-weight: normal; align: center; background: #ffffcc;" \| 0		! style="font-weight: normal; align: center; background: #ffffcc;" \| 0
	! style="font-weight: normal; text-align: right; background: #ffffcc;" \| <tt>aaabaaaaa$</tt>		! style="font-weight: normal; text-align: right; background: #ffffcc;" \| <tt>aaabaaaaa$</tt>
	! style="font-weight: normal; align: center; background: #ffffcc;" \|		! style="font-weight: normal; align: center; background: #ffffcc;" \| 1
	\|-		\|-
	! style="font-weight: normal; align: center; background: #ffffcc;" \|		! style="font-weight: normal; align: center; background: #ffffcc;" \| 1
	! style="font-weight: normal; text-align: right; background: #ffffcc;" \| <tt>$</tt>		! style="font-weight: normal; text-align: right; background: #ffffcc;" \| <tt>aabaaaaa$</tt>
	! style="font-weight: normal; align: center; background: #ffffcc;" \|		! style="font-weight: normal; align: center; background: #ffffcc;" \| 3
	\|-		\|-
	! style="font-weight: normal; align: center; background: #ffffcc;" \|		! style="font-weight: normal; align: center; background: #ffffcc;" \| 3
	! style="font-weight: normal; text-align: right; background: #ffffcc;" \| <tt>$</tt>		! style="font-weight: normal; text-align: right; background: #ffffcc;" \| <tt>abaaaaa$</tt>
	! style="font-weight: normal; align: center; background: #ffffcc;" \|		! style="font-weight: normal; align: center; background: #ffffcc;" \| 4
	\|-		\|-
	! style="font-weight: normal; align: center; background: #~~e6e6e6~~;" \|		! style="font-weight: normal; align: center; background: #e6bbaf;" \| 4
	! style="font-weight: normal; text-align: right; background: #~~e6e6e6~~;" \| <tt>$</tt>		! style="font-weight: normal; text-align: right; background: #e6bbaf;" \| <tt>baaaaa$</tt>
	! style="font-weight: normal; align: center; background: #~~e6e6e6~~;" \|		! style="font-weight: normal; align: center; background: #e6bbaf;" \| error (backtracking)
	\|-		\|-
	! style="font-weight: normal; align: center; background: #~~e6e6e6~~;" \|		! style="font-weight: normal; align: center; background: #ffffcc;" \| 3
	! style="font-weight: normal; text-align: right; background: #~~e6e6e6~~;" \| <tt>$</tt>		! style="font-weight: normal; text-align: right; background: #ffffcc;" \| <tt>abaaaaa$</tt>
	! style="font-weight: normal; align: center; background: #~~e6e6e6~~;" \|		! style="font-weight: normal; align: center; background: #ffffcc;" \| '''T1''' (aa)
	\|-		\|-
	! style="font-weight: normal; align: center; background: #ffffcc;" \|		! style="font-weight: normal; align: center; background: #e6e6e6;" \| 0
	! style="font-weight: normal; text-align: right; background: #ffffcc;" \| <tt>$</tt>		! style="font-weight: normal; text-align: right; background: #e6e6e6;" \| <tt>abaaaaa$</tt>
	! style="font-weight: normal; align: center; background: #ffffcc;" \|		! style="font-weight: normal; align: center; background: #e6e6e6;" \| 1
			\|-
			! style="font-weight: normal; align: center; background: #e6e6e6;" \| 1
			! style="font-weight: normal; text-align: right; background: #e6e6e6;" \| <tt>baaaaa$</tt>
			! style="font-weight: normal; align: center; background: #e6e6e6;" \| '''T3''' (a)
			\|-
			! style="font-weight: normal; align: center; background: #ffffcc;" \| 0
			! style="font-weight: normal; text-align: right; background: #ffffcc;" \| <tt>baaaaa$</tt>
			! style="font-weight: normal; align: center; background: #ffffcc;" \| 2
			\|-
			! style="font-weight: normal; align: center; background: #ffffcc;" \| 2
			! style="font-weight: normal; text-align: right; background: #ffffcc;" \| <tt>aaaaa$</tt>
			! style="font-weight: normal; align: center; background: #ffffcc;" \| '''T3''' (b)
			\|-
			! style="font-weight: normal; align: center; background: #e6e6e6;" \| 0
			! style="font-weight: normal; text-align: right; background: #e6e6e6;" \| <tt>aaaaa$</tt>
			! style="font-weight: normal; align: center; background: #e6e6e6;" \| 1
			\|-
			! style="font-weight: normal; align: center; background: #e6e6e6;" \| 1
			! style="font-weight: normal; text-align: right; background: #e6e6e6;" \| <tt>aaaa$</tt>
			! style="font-weight: normal; align: center; background: #e6e6e6;" \| 3
			\|-
			! style="font-weight: normal; align: center; background: #e6e6e6;" \| 3
			! style="font-weight: normal; text-align: right; background: #e6e6e6;" \| <tt>aaa$</tt>
			! style="font-weight: normal; align: center; background: #e6e6e6;" \| 4
			\|-
			! style="font-weight: normal; align: center; background: #e6e6e6;" \| 4
			! style="font-weight: normal; text-align: right; background: #e6e6e6;" \| <tt>aa$</tt>
			! style="font-weight: normal; align: center; background: #e6e6e6;" \| 5
	\|-		\|-
	! style="font-weight: normal; align: center; background: #~~ffffcc~~;" \|		! style="font-weight: normal; align: center; background: #e6e6e6;" \| 5
	! style="font-weight: normal; text-align: right; background: #~~ffffcc~~;" \| <tt>$</tt>		! style="font-weight: normal; text-align: right; background: #e6e6e6;" \| <tt>a$</tt>
	! style="font-weight: normal; align: center; background: #~~ffffcc~~;" \|		! style="font-weight: normal; align: center; background: #e6e6e6;" \| '''T2''' (aaaa)
	\|-		\|-
	! style="font-weight: normal; align: center; background: #ffffcc;" \|		! style="font-weight: normal; align: center; background: #ffffcc;" \| 0
	! style="font-weight: normal; text-align: right; background: #ffffcc;" \| <tt>$</tt>		! style="font-weight: normal; text-align: right; background: #ffffcc;" \| <tt>a$</tt>
	! style="font-weight: normal; align: center; background: #ffffcc;" \|		! style="font-weight: normal; align: center; background: #ffffcc;" \| 1
	\|-		\|-
	! style="font-weight: normal; align: center; background: #ffffcc;" \|		! style="font-weight: normal; align: center; background: #ffffcc;" \| 1
	! style="font-weight: normal; text-align: right; background: #ffffcc;" \| <tt>$</tt>		! style="font-weight: normal; text-align: right; background: #ffffcc;" \| <tt>$</tt>
	! style="font-weight: normal; align: center; background: #ffffcc;" \|		! style="font-weight: normal; align: center; background: #ffffcc;" \| '''T3''' (a)
	\|}		\|}

← Older revision		Revision as of 18:17, 22 March 2009
Line 180:		Line 180:
	! style="font-weight: normal; align: center; background: #ffffcc;" \| 0		! style="font-weight: normal; align: center; background: #ffffcc;" \| 0
	! style="font-weight: normal; text-align: right; background: #ffffcc;" \| <tt>aaabaaaaa$</tt>		! style="font-weight: normal; text-align: right; background: #ffffcc;" \| <tt>aaabaaaaa$</tt>
	! style="font-weight: normal; align: center; background: #ffffcc;" \|		! style="font-weight: normal; align: center; background: #ffffcc;" \| 1
	\|-		\|-
	! style="font-weight: normal; align: center; background: #ffffcc;" \|		! style="font-weight: normal; align: center; background: #ffffcc;" \| 1
	! style="font-weight: normal; text-align: right; background: #ffffcc;" \| <tt>$</tt>		! style="font-weight: normal; text-align: right; background: #ffffcc;" \| <tt>aabaaaaa$</tt>
	! style="font-weight: normal; align: center; background: #ffffcc;" \|		! style="font-weight: normal; align: center; background: #ffffcc;" \| 3
	\|-		\|-
	! style="font-weight: normal; align: center; background: #ffffcc;" \|		! style="font-weight: normal; align: center; background: #ffffcc;" \| 3
	! style="font-weight: normal; text-align: right; background: #ffffcc;" \| <tt>$</tt>		! style="font-weight: normal; text-align: right; background: #ffffcc;" \| <tt>abaaaaa$</tt>
	! style="font-weight: normal; align: center; background: #ffffcc;" \|		! style="font-weight: normal; align: center; background: #ffffcc;" \| 4
	\|-		\|-
	! style="font-weight: normal; align: center; background: #~~e6e6e6~~;" \|		! style="font-weight: normal; align: center; background: #e6bbaf;" \| 4
	! style="font-weight: normal; text-align: right; background: #~~e6e6e6~~;" \| <tt>$</tt>		! style="font-weight: normal; text-align: right; background: #e6bbaf;" \| <tt>baaaaa$</tt>
	! style="font-weight: normal; align: center; background: #~~e6e6e6~~;" \|		! style="font-weight: normal; align: center; background: #e6bbaf;" \| error (backtracking)
	\|-		\|-
	! style="font-weight: normal; align: center; background: #~~e6e6e6~~;" \|		! style="font-weight: normal; align: center; background: #ffffcc;" \| 3
	! style="font-weight: normal; text-align: right; background: #~~e6e6e6~~;" \| <tt>$</tt>		! style="font-weight: normal; text-align: right; background: #ffffcc;" \| <tt>abaaaaa$</tt>
	! style="font-weight: normal; align: center; background: #~~e6e6e6~~;" \|		! style="font-weight: normal; align: center; background: #ffffcc;" \| '''T1''' (aa)
	\|-		\|-
	! style="font-weight: normal; align: center; background: #ffffcc;" \|		! style="font-weight: normal; align: center; background: #e6e6e6;" \| 0
	! style="font-weight: normal; text-align: right; background: #ffffcc;" \| <tt>$</tt>		! style="font-weight: normal; text-align: right; background: #e6e6e6;" \| <tt>abaaaaa$</tt>
	! style="font-weight: normal; align: center; background: #ffffcc;" \|		! style="font-weight: normal; align: center; background: #e6e6e6;" \| 1
			\|-
			! style="font-weight: normal; align: center; background: #e6e6e6;" \| 1
			! style="font-weight: normal; text-align: right; background: #e6e6e6;" \| <tt>baaaaa$</tt>
			! style="font-weight: normal; align: center; background: #e6e6e6;" \| '''T3''' (a)
			\|-
			! style="font-weight: normal; align: center; background: #ffffcc;" \| 0
			! style="font-weight: normal; text-align: right; background: #ffffcc;" \| <tt>baaaaa$</tt>
			! style="font-weight: normal; align: center; background: #ffffcc;" \| 2
			\|-
			! style="font-weight: normal; align: center; background: #ffffcc;" \| 2
			! style="font-weight: normal; text-align: right; background: #ffffcc;" \| <tt>aaaaa$</tt>
			! style="font-weight: normal; align: center; background: #ffffcc;" \| '''T3''' (b)
			\|-
			! style="font-weight: normal; align: center; background: #e6e6e6;" \| 0
			! style="font-weight: normal; text-align: right; background: #e6e6e6;" \| <tt>aaaaa$</tt>
			! style="font-weight: normal; align: center; background: #e6e6e6;" \| 1
			\|-
			! style="font-weight: normal; align: center; background: #e6e6e6;" \| 1
			! style="font-weight: normal; text-align: right; background: #e6e6e6;" \| <tt>aaaa$</tt>
			! style="font-weight: normal; align: center; background: #e6e6e6;" \| 3
			\|-
			! style="font-weight: normal; align: center; background: #e6e6e6;" \| 3
			! style="font-weight: normal; text-align: right; background: #e6e6e6;" \| <tt>aaa$</tt>
			! style="font-weight: normal; align: center; background: #e6e6e6;" \| 4
			\|-
			! style="font-weight: normal; align: center; background: #e6e6e6;" \| 4
			! style="font-weight: normal; text-align: right; background: #e6e6e6;" \| <tt>aa$</tt>
			! style="font-weight: normal; align: center; background: #e6e6e6;" \| 5
	\|-		\|-
	! style="font-weight: normal; align: center; background: #~~ffffcc~~;" \|		! style="font-weight: normal; align: center; background: #e6e6e6;" \| 5
	! style="font-weight: normal; text-align: right; background: #~~ffffcc~~;" \| <tt>$</tt>		! style="font-weight: normal; text-align: right; background: #e6e6e6;" \| <tt>a$</tt>
	! style="font-weight: normal; align: center; background: #~~ffffcc~~;" \|		! style="font-weight: normal; align: center; background: #e6e6e6;" \| '''T2''' (aaaa)
	\|-		\|-
	! style="font-weight: normal; align: center; background: #ffffcc;" \|		! style="font-weight: normal; align: center; background: #ffffcc;" \| 0
	! style="font-weight: normal; text-align: right; background: #ffffcc;" \| <tt>$</tt>		! style="font-weight: normal; text-align: right; background: #ffffcc;" \| <tt>a$</tt>
	! style="font-weight: normal; align: center; background: #ffffcc;" \|		! style="font-weight: normal; align: center; background: #ffffcc;" \| 1
	\|-		\|-
	! style="font-weight: normal; align: center; background: #ffffcc;" \|		! style="font-weight: normal; align: center; background: #ffffcc;" \| 1
	! style="font-weight: normal; text-align: right; background: #ffffcc;" \| <tt>$</tt>		! style="font-weight: normal; text-align: right; background: #ffffcc;" \| <tt>$</tt>
	! style="font-weight: normal; align: center; background: #ffffcc;" \|		! style="font-weight: normal; align: center; background: #ffffcc;" \| '''T3''' (a)
	\|}		\|}