Theoretical Aspects of Lexical Analysis/Exercise 7 - Revision history

Root at 18:42, 26 April 2026

2026-04-26T18:42:29Z

← Older revision		Revision as of 18:42, 26 April 2026
Line 7:		Line 7:
	The following is the result of applying Thompson's algorithm. State '''8''' recognizes the first expression (token '''T1'''); state '''12''' recognizes token '''T2'''; and state '''20''' recognizes token '''T3'''.		The following is the result of applying Thompson's algorithm. State '''8''' recognizes the first expression (token '''T1'''); state '''12''' recognizes token '''T2'''; and state '''20''' 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 48:		Line 48:
	fontsize=10		fontsize=10
	}		}
	</~~dot-hack~~>		</kroki>

	== DFA ==		== DFA ==
Line 130:		Line 130:
	Graphically, the DFA is represented as follows:		Graphically, the DFA is represented as follows:

	<~~dot-hack~~>		<kroki lang="graphviz">
	digraph dfa {		digraph dfa {
	{ node [shape=circle style=invis] s }		{ node [shape=circle style=invis] s }
Line 145:		Line 145:
	fontsize=10		fontsize=10
	}		}
	</~~dot-hack~~>		</kroki>

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

	Given the minimization tree, the final minimal DFA is as follows. Note that states 2 and 4 cannot be the same since they recognize different tokens.		Given the minimization tree, the final minimal DFA is as follows. Note that states 2 and 4 cannot be the same since they recognize different tokens.

	<~~dot-hack~~>		<kroki lang="graphviz">
	digraph mindfa {		digraph mindfa {
	{ node [shape=circle style=invis] s }		{ node [shape=circle style=invis] s }
Line 181:		Line 181:
	fontsize=10		fontsize=10
	}		}
	</~~dot-hack~~>		</kroki>

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

Root: /* DFA */

2023-05-09T17:25:11Z

DFA

← Older revision		Revision as of 17:25, 9 May 2023
Line 160:		Line 160:
	"{0, 1, 3}" -> "{0}" [label=" b",fontsize=10]		"{0, 1, 3}" -> "{0}" [label=" b",fontsize=10]
	"{0, 1, 3}" -> "{1,3}"		"{0, 1, 3}" -> "{1,3}"
			"{1,3}" -> "{1,3} " [label=" a,b",fontsize=10]
	fontsize=10		fontsize=10
	}		}
	</dot-hack>		</dot-hack>

	~~The tree expansion for non-splitting sets has been omitted for simplicity ("a" transitions for super-state {0, 1, 3}, and "a" and "b" transitions for super-state {1,3}).~~

	Given the minimization tree, the final minimal DFA is as follows. Note that states 2 and 4 cannot be the same since they recognize different tokens.		Given the minimization tree, the final minimal DFA is as follows. Note that states 2 and 4 cannot be the same since they recognize different tokens.

Root at 10:16, 12 February 2019

2019-02-12T10:16:03Z

← Older revision		Revision as of 10:16, 12 February 2019
Line 7:		Line 7:
	The following is the result of applying Thompson's algorithm. State '''8''' recognizes the first expression (token '''T1'''); state '''12''' recognizes token '''T2'''; and state '''20''' recognizes token '''T3'''.		The following is the result of applying Thompson's algorithm. State '''8''' recognizes the first expression (token '''T1'''); state '''12''' recognizes token '''T2'''; and state '''20''' recognizes token '''T3'''.

	<~~graph~~>		<dot-hack>
	digraph nfa {		digraph nfa {
	{ node [shape=circle style=invis] s }		{ node [shape=circle style=invis] s }
Line 48:		Line 48:
	fontsize=10		fontsize=10
	}		}
	</~~graph~~>		</dot-hack>

	== DFA ==		== DFA ==
Line 130:		Line 130:
	Graphically, the DFA is represented as follows:		Graphically, the DFA is represented as follows:

	<~~graph~~>		<dot-hack>
	digraph dfa {		digraph dfa {
	{ node [shape=circle style=invis] s }		{ node [shape=circle style=invis] s }
Line 145:		Line 145:
	fontsize=10		fontsize=10
	}		}
	</~~graph~~>		</dot-hack>

	The minimization tree is as follows. Note that before considering transition behavior, states are split according to the token they recognize.		The minimization tree is as follows. 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 157:		Line 157:
	"{0, 1, 2, 3, 4} " -> "{4}" [label=" T3",fontsize=10]		"{0, 1, 2, 3, 4} " -> "{4}" [label=" T3",fontsize=10]
	"{0, 1, 2, 3}" -> "{0, 1, 3}" [label=" a",fontsize=10]		"{0, 1, 2, 3}" -> "{0, 1, 3}" [label=" a",fontsize=10]
	"{0, 1, 2, 3}" -> "{2}" ~~//[label=" a",fontsize=10]~~		"{0, 1, 2, 3}" -> "{2}"
	"{0, 1, 3}" -> "{0}" [label=" b",fontsize=10]		"{0, 1, 3}" -> "{0}" [label=" b",fontsize=10]
	"{0, 1, 3}" -> "{1,3}" ~~//[label=" b",fontsize=10]~~		"{0, 1, 3}" -> "{1,3}"
	fontsize=10		fontsize=10
	~~//label="Minimization tree"~~
	}		}
	</~~graph~~>		</dot-hack>

	The tree expansion for non-splitting sets has been omitted for simplicity ("a" transitions for super-state {0, 1, 3}, and "a" and "b" transitions for super-state {1,3}).		The tree expansion for non-splitting sets has been omitted for simplicity ("a" transitions for super-state {0, 1, 3}, and "a" and "b" transitions for super-state {1,3}).
Line 169:		Line 168:
	Given the minimization tree, the final minimal DFA is as follows. Note that states 2 and 4 cannot be the same since they recognize different tokens.		Given the minimization tree, the final minimal DFA is as follows. Note that states 2 and 4 cannot be the same since they recognize different tokens.

	<~~graph~~>		<dot-hack>
	digraph mindfa {		digraph mindfa {
	{ node [shape=circle style=invis] s }		{ node [shape=circle style=invis] s }
Line 183:		Line 182:
	fontsize=10		fontsize=10
	}		}
	</~~graph~~>		</dot-hack>

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

Root at 14:39, 6 April 2015

2015-04-06T14:39:03Z

← Older revision		Revision as of 14:39, 6 April 2015
Line 235:		Line 235:
	The input string ''aababb'' is, after 10 steps, split into three tokens: '''T1''' (corresponding to lexeme ''aa''), '''T1''' (''b''), '''T1''' (''a''), and '''T3''' (''bb'').		The input string ''aababb'' is, after 10 steps, split into three tokens: '''T1''' (corresponding to lexeme ''aa''), '''T1''' (''b''), '''T1''' (''a''), and '''T3''' (''bb'').

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

Root: /* NFA */

2012-03-04T22:46:30Z

NFA

← Older revision		Revision as of 22:46, 4 March 2012
Line 44:		Line 44:
	16 -> 17		16 -> 17
	17 -> 20		17 -> 20
	18 -> 19 [label="b",fontsize=10]		18 -> 19 [label="a",fontsize=10]
	19 -> 20		19 -> 20
	fontsize=10		fontsize=10

Root at 17:38, 28 March 2009

2009-03-28T17:38:17Z

← Older revision		Revision as of 17:38, 28 March 2009
Line 166:		Line 166:

	The tree expansion for non-splitting sets has been omitted for simplicity ("a" transitions for super-state {0, 1, 3}, and "a" and "b" transitions for super-state {1,3}).		The tree expansion for non-splitting sets has been omitted for simplicity ("a" transitions for super-state {0, 1, 3}, and "a" and "b" transitions for super-state {1,3}).
	~~<!--~~
	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 as follows. Note that states 2 and 4 cannot be the same since they recognize different tokens.
	-->
			<graph>
			digraph mindfa {
			{ node [shape=circle style=invis] s }
			rankdir=LR; ratio=0.5
			node [shape=doublecircle,fixedsize=true,width=0.2,fontsize=10]; 0 13 2 4
			node [shape=circle,fixedsize=true,width=0.2,fontsize=10];
			s -> 0
			0 -> 13 [label="a",fontsize=10]
			0 -> 2 [label="b",fontsize=10]
			13 -> 13 [label="a",fontsize=10]
			2 -> 4 [label="b",fontsize=10]
			4 -> 4 [label="b",fontsize=10]
			fontsize=10
			}
			</graph>

	== Input Analysis ==		== Input Analysis ==
	~~<!--~~
	{\| 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 177:		Line 193:
	\|-		\|-
	! 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>~~abaabb~~$</tt>		! style="font-weight: normal; text-align: right; background: #ffffcc;" \| <tt>aababb$</tt>
	! style="font-weight: normal; align: center; background: #ffffcc;" \| 1		! style="font-weight: normal; align: center; background: #ffffcc;" \| 13
	\|-		\|-
	! style="font-weight: normal; align: center; background: #ffffcc;" \| 1		! style="font-weight: normal; align: center; background: #ffffcc;" \| 13
	! style="font-weight: normal; text-align: right; background: #ffffcc;" \| <tt>~~baabb~~$</tt>		! style="font-weight: normal; text-align: right; background: #ffffcc;" \| <tt>ababb$</tt>
	! style="font-weight: normal; align: center; background: #ffffcc;" \| 3		! style="font-weight: normal; align: center; background: #ffffcc;" \| 13
	\|-		\|-
	! style="font-weight: normal; align: center; background: #ffffcc;" \| 3		! style="font-weight: normal; align: center; background: #ffffcc;" \| 13
	! style="font-weight: normal; text-align: right; background: #ffffcc;" \| <tt>~~aabb~~$</tt>		! style="font-weight: normal; text-align: right; background: #ffffcc;" \| <tt>babb$</tt>
	! style="font-weight: normal; align: center; background: #ffffcc;" \| '''T1'''		! style="font-weight: normal; align: center; background: #ffffcc;" \| '''T1''' (aa)
	\|-		\|-
	! style="font-weight: normal; align: center; background: #e6e6e6;" \| 0		! style="font-weight: normal; align: center; background: #e6e6e6;" \| 0
	! style="font-weight: normal; text-align: right; background: #e6e6e6;" \| <tt>~~aabb~~$</tt>		! style="font-weight: normal; text-align: right; background: #e6e6e6;" \| <tt>babb$</tt>
	! style="font-weight: normal; align: center; background: #e6e6e6;" \| 1		! style="font-weight: normal; align: center; background: #e6e6e6;" \| 2
	\|-		\|-
	! style="font-weight: normal; align: center; background: #e6e6e6;" \| 1		! style="font-weight: normal; align: center; background: #e6e6e6;" \| 2
	! style="font-weight: normal; text-align: right; background: #e6e6e6;" \| <tt>abb$</tt>		! style="font-weight: normal; text-align: right; background: #e6e6e6;" \| <tt>abb$</tt>
	! style="font-weight: normal; align: center; background: #e6e6e6;" \| '''T2'''		! style="font-weight: normal; align: center; background: #e6e6e6;" \| '''T1''' (b)
	\|-		\|-
	! 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>abb$</tt>		! style="font-weight: normal; text-align: right; background: #ffffcc;" \| <tt>abb$</tt>
	! style="font-weight: normal; align: center; background: #ffffcc;" \| 1		! style="font-weight: normal; align: center; background: #ffffcc;" \| 13
	\|-		\|-
	! style="font-weight: normal; align: center; background: #ffffcc;" \| 1		! style="font-weight: normal; align: center; background: #ffffcc;" \| 13
	! style="font-weight: normal; text-align: right; background: #ffffcc;" \| <tt>bb$</tt>		! style="font-weight: normal; text-align: right; background: #ffffcc;" \| <tt>bb$</tt>
	! style="font-weight: normal; align: center; background: #ffffcc;" \| 3		! style="font-weight: normal; align: center; background: #ffffcc;" \| '''T1''' (a)
	\|-		\|-
	! style="font-weight: normal; align: center; background: #~~ffffcc~~;" \| 3		! style="font-weight: normal; align: center; background: #e6e6e6;" \| 0
	! style="font-weight: normal; text-align: right; background: #~~ffffcc~~;" \| <tt>b$</tt>		! style="font-weight: normal; text-align: right; background: #e6e6e6;" \| <tt>bb$</tt>
	! style="font-weight: normal; align: center; background: #~~ffffcc~~;" \| 4		! style="font-weight: normal; align: center; background: #e6e6e6;" \| 2
	\|-		\|-
	! style="font-weight: normal; align: center; background: #~~ffffcc~~;" \| 4		! style="font-weight: normal; align: center; background: #e6e6e6;" \| 2
	! style="font-weight: normal; text-align: right; background: #~~ffffcc~~;" \| <tt>$</tt>		! style="font-weight: normal; text-align: right; background: #e6e6e6;" \| <tt>b$</tt>
	! style="font-weight: normal; align: center; background: #~~ffffcc~~;" \| '''T2'''		! 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>$</tt>
			! style="font-weight: normal; align: center; background: #e6e6e6;" \| '''T3''' (bb)
	\|}		\|}

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

Root: New page: NOTOC Compute the non-deterministic finite automaton (NFA) by using Thompson's algorithm. Compute the minimal deterministic finite automaton (DFA).
The alphabet is Σ = { a, b }. I...

2009-03-28T16:45:47Z

New page: __NOTOC__ Compute the non-deterministic finite automaton (NFA) by using Thompson's algorithm. Compute the minimal deterministic finite automaton (DFA). The alphabet is Σ = { a, b }. I...

New page

__NOTOC__
Compute the non-deterministic finite automaton (NFA) by using Thompson's algorithm. Compute the minimal deterministic finite automaton (DFA). The alphabet is Σ = { a, b }. Indicate the number of processing steps for the given input string.
* <nowiki>G = { a*|b, a*, b*|a }</nowiki>, input string = aababb

== NFA ==

The following is the result of applying Thompson's algorithm. State '''8''' recognizes the first expression (token '''T1'''); state '''12''' recognizes token '''T2'''; and state '''20''' recognizes token '''T3'''.

<graph>
digraph nfa {
{ node [shape=circle style=invis] s }
rankdir=LR; ratio=0.5
node [shape=doublecircle,fixedsize=true,width=0.2,fontsize=10]; 8 12 20
node [shape=circle,fixedsize=true,width=0.2,fontsize=10];

s -> 0

0 -> 1
1 -> 2
1 -> 6
2 -> 3
2 -> 5
3 -> 4 [label="a",fontsize=10]
4 -> 3
4 -> 5
5 -> 8
6 -> 7 [label="b",fontsize=10]
7 -> 8

0 -> 9
9 -> 10
9 -> 12
10 -> 11 [label="a",fontsize=10]
11 -> 10
11 -> 12

0 -> 13
13 -> 14
13 -> 18
14 -> 15
14 -> 17
15 -> 16 [label="b",fontsize=10]
16 -> 15
16 -> 17
17 -> 20
18 -> 19 [label="b",fontsize=10]
19 -> 20
fontsize=10
}
</graph>

== DFA ==

Determination table for the above NFA:

{| cellspacing="2"
! style="padding-left: 20px; padding-right: 20px; background: wheat;" | In
! style="padding-left: 20px; padding-right: 20px; background: wheat;" | α∈Σ
! style="padding-left: 20px; padding-right: 20px; background: wheat;" | move(In, α)
! style="padding-left: 20px; padding-right: 20px; background: wheat;" | ε-closure(move(In, α))
! style="padding-left: 20px; padding-right: 20px; background: wheat;" | In+1 = ε-closure(move(In, α))
|-
! style="font-weight: normal; align: center; background: #ffffcc;" | -
! style="font-weight: normal; align: center; background: #ffffcc;" | -
! style="font-weight: normal; align: center; background: #ffffcc;" | 0
! style="font-weight: normal; align: left; background: #ffffcc;" | 0, 1, 2, 3, 5, 6, '''8''', 9, 10, '''12''', 13, 14, 15, 17, 18, '''20'''
! style="font-weight: normal; align: center; background: #ffffcc;" | '''0''' (T1)
|-
! style="font-weight: normal; align: center; background: #e6e6e6;" | 0
! style="font-weight: normal; align: center; background: #e6e6e6;" | a
! style="font-weight: normal; align: center; background: #e6e6e6;" | 4, 11, 19
! style="font-weight: normal; align: left; background: #e6e6e6;" | 3, 4, 5, '''8''', 10, 11, '''12''', 19, '''20'''
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''1''' (T1)
|-
! style="font-weight: normal; align: center; background: #e6e6e6;" | 0
! style="font-weight: normal; align: center; background: #e6e6e6;" | b
! style="font-weight: normal; align: center; background: #e6e6e6;" | 7, 16
! style="font-weight: normal; align: left; background: #e6e6e6;" | 7, '''8''', 15, 16, 17, '''20'''
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''2''' (T1)
|-
! style="font-weight: normal; align: center; background: #ffffcc;" | 1
! style="font-weight: normal; align: center; background: #ffffcc;" | a
! style="font-weight: normal; align: center; background: #ffffcc;" | 4, 11
! style="font-weight: normal; align: left; background: #ffffcc;" | 3, 4, 5, '''8''', 10, 11, '''12'''
! style="font-weight: normal; align: center; background: #ffffcc;" | '''3''' (T1)
|-
! style="font-weight: normal; align: center; background: #ffffcc;" | 1
! style="font-weight: normal; align: center; background: #ffffcc;" | b
! style="font-weight: normal; align: center; background: #ffffcc;" | -
! style="font-weight: normal; align: left; background: #ffffcc;" | -
! style="font-weight: normal; align: center; background: #ffffcc;" | -
|-
! style="font-weight: normal; align: center; background: #e6e6e6;" | 2
! style="font-weight: normal; align: center; background: #e6e6e6;" | a
! style="font-weight: normal; align: center; background: #e6e6e6;" | -
! style="font-weight: normal; align: left; background: #e6e6e6;" | -
! style="font-weight: normal; align: center; background: #e6e6e6;" | -
|-
! style="font-weight: normal; align: center; background: #e6e6e6;" | 2
! style="font-weight: normal; align: center; background: #e6e6e6;" | b
! style="font-weight: normal; align: center; background: #e6e6e6;" | 16
! style="font-weight: normal; align: left; background: #e6e6e6;" | 15, 16, 17, '''20'''
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''4''' (T3)
|-
! style="font-weight: normal; align: center; background: #ffffcc;" | 3
! style="font-weight: normal; align: center; background: #ffffcc;" | a
! style="font-weight: normal; align: center; background: #ffffcc;" | 4, 11
! style="font-weight: normal; align: left; background: #ffffcc;" | 3, 4, 5, '''8''', 10, 11, '''12'''
! style="font-weight: normal; align: center; background: #ffffcc;" | '''3''' (T1)
|-
! style="font-weight: normal; align: center; background: #ffffcc;" | 3
! style="font-weight: normal; align: center; background: #ffffcc;" | b
! style="font-weight: normal; align: center; background: #ffffcc;" | -
! style="font-weight: normal; align: left; background: #ffffcc;" | -
! style="font-weight: normal; align: center; background: #ffffcc;" | -
|-
! style="font-weight: normal; align: center; background: #e6e6e6;" | 4
! style="font-weight: normal; align: center; background: #e6e6e6;" | a
! style="font-weight: normal; align: center; background: #e6e6e6;" | -
! style="font-weight: normal; align: left; background: #e6e6e6;" | -
! style="font-weight: normal; align: center; background: #e6e6e6;" | -
|-
! style="font-weight: normal; align: center; background: #e6e6e6;" | 4
! style="font-weight: normal; align: center; background: #e6e6e6;" | b
! style="font-weight: normal; align: center; background: #e6e6e6;" | 16
! style="font-weight: normal; align: left; background: #e6e6e6;" | 15, 16, 17, '''20'''
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''4''' (T3)
|}

Graphically, the DFA is represented as follows:

<graph>
digraph dfa {
{ node [shape=circle style=invis] s }
rankdir=LR; ratio=0.5
node [shape=doublecircle,fixedsize=true,width=0.2,fontsize=10]; 0 1 2 3 4
node [shape=circle,fixedsize=true,width=0.2,fontsize=10];
s -> 0
0 -> 1 [label="a",fontsize=10]
0 -> 2 [label="b",fontsize=10]
1 -> 3 [label="a",fontsize=10]
2 -> 4 [label="b",fontsize=10]
3 -> 3 [label="a",fontsize=10]
4 -> 4 [label="b",fontsize=10]
fontsize=10
}
</graph>

The minimization tree is as follows. Note that before considering transition behavior, states are split according to the token they recognize.

<graph>
digraph mintree {
node [shape=none,fixedsize=true,width=0.3,fontsize=10]
"{0, 1, 2, 3, 4}" -> "{}" [label="NF",fontsize=10]
"{0, 1, 2, 3, 4}" -> "{0, 1, 2, 3, 4} " [label=" F",fontsize=10]
"{0, 1, 2, 3, 4} " -> "{0, 1, 2, 3}" [label=" T1",fontsize=10]
"{0, 1, 2, 3, 4} " -> "{4}" [label=" T3",fontsize=10]
"{0, 1, 2, 3}" -> "{0, 1, 3}" [label=" a",fontsize=10]
"{0, 1, 2, 3}" -> "{2}" //[label=" a",fontsize=10]
"{0, 1, 3}" -> "{0}" [label=" b",fontsize=10]
"{0, 1, 3}" -> "{1,3}" //[label=" b",fontsize=10]
fontsize=10
//label="Minimization tree"
}
</graph>

The tree expansion for non-splitting sets has been omitted for simplicity ("a" transitions for super-state {0, 1, 3}, and "a" and "b" transitions for super-state {1,3}).

== Input Analysis ==

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