Theoretical Aspects of Lexical Analysis/Exercise 15 - Revision history

Root at 18:50, 26 April 2026

2026-04-26T18:50:46Z

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

	== DFA ==		== DFA ==
Line 198:		Line 198:
	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 216:		Line 216:
	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 237:		Line 237:
	fontsize=10		fontsize=10
	}		}
	</~~dot-hack~~>		</kroki>

	Given the minimization tree, the final minimal DFA is as follows.		Given the minimization tree, the final minimal DFA is as follows.

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

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

Root at 10:30, 12 February 2019

2019-02-12T10:30:20Z

← Older revision		Revision as of 10:30, 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 '''16''' recognizes token '''T2'''; and state '''21''' recognizes token '''T3'''.		The following is the result of applying Thompson's algorithm. State '''8''' recognizes the first expression (token '''T1'''); state '''16''' recognizes token '''T2'''; and state '''21''' recognizes token '''T3'''.

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

	== DFA ==		== DFA ==
Line 198:		Line 198:
	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 216:		Line 216:
	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 229:		Line 229:
	"{0, 1, 2, 3, 4, 5, 6} " -> "{6}" [label=" T3",fontsize=10]		"{0, 1, 2, 3, 4, 5, 6} " -> "{6}" [label=" T3",fontsize=10]
	"{0, 1, 3, 4}" -> "{0, 1, 4}" [label=" a",fontsize=10]		"{0, 1, 3, 4}" -> "{0, 1, 4}" [label=" a",fontsize=10]
	"{0, 1, 3, 4}" -> "{3}" ~~//[label=" a",fontsize=10]~~		"{0, 1, 3, 4}" -> "{3}"
	"{2, 5}" -> "{2}" [label=" c",fontsize=10]		"{2, 5}" -> "{2}" [label=" c",fontsize=10]
	"{2, 5}" -> "{5}" ~~//[label=" c",fontsize=10]~~		"{2, 5}" -> "{5}"
	"{0, 1, 4}" -> "{0}" [label=" b",fontsize=10]		"{0, 1, 4}" -> "{0}" [label=" b",fontsize=10]
	"{0, 1, 4}" -> "{1, 4}" ~~//[label=" b",fontsize=10]~~		"{0, 1, 4}" -> "{1, 4}"
	"{1, 4}" -> "{1, 4} " [label=" a, b, c",fontsize=10]		"{1, 4}" -> "{1, 4} " [label=" a, b, c",fontsize=10]
	fontsize=10		fontsize=10
	~~//label="Minimization tree"~~
	}		}
	</~~graph~~>		</dot-hack>

	Given the minimization tree, the final minimal DFA is as follows.		Given the minimization tree, the final minimal DFA is as follows.

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

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

Root at 14:37, 6 April 2015

2015-04-06T14:37:04Z

← Older revision		Revision as of 14:37, 6 April 2015
Line 324:		Line 324:
	The input string ''aaabcacc'' is, after 13 steps, split into five tokens: '''T1''' (corresponding to lexeme ''aaa''), '''T3''' (''bc''), '''T1''' (''a''), '''T1''' (''c''), '''T1''' (''c'').		The input string ''aaabcacc'' is, after 13 steps, split into five tokens: '''T1''' (corresponding to lexeme ''aaa''), '''T3''' (''bc''), '''T1''' (''a''), '''T1''' (''c''), '''T1''' (''c'').

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

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

Root: /* DFA */

2011-03-31T19:53:02Z

DFA

← Older revision		Revision as of 19:53, 31 March 2011
Line 167:		Line 167:
	! style="font-weight: normal; align: center; background: #ffffcc;" \| 5		! style="font-weight: normal; align: center; background: #ffffcc;" \| 5
	! style="font-weight: normal; align: center; background: #ffffcc;" \| b		! style="font-weight: normal; align: center; background: #ffffcc;" \| b
	! style="font-weight: normal; align: center; background: #ffffcc;" \| 4		! style="font-weight: normal; align: center; background: #ffffcc;" \| 14
	! style="font-weight: normal; align: left; background: #ffffcc;" \| 3, 4, 5, '''8'''		! style="font-weight: normal; align: left; background: #ffffcc;" \| 13, 14, 15, '''16'''
	! style="font-weight: normal; align: center; background: #ffffcc;" \| '''4''' (T1)		! style="font-weight: normal; align: center; background: #ffffcc;" \| '''5''' (T2)
	\|-		\|-
	! style="font-weight: normal; align: center; background: #ffffcc;" \| 5		! style="font-weight: normal; align: center; background: #ffffcc;" \| 5

Root: /* Input Analysis */

2010-04-22T19:14:21Z

Input Analysis

← Older revision		Revision as of 19:14, 22 April 2010
Line 322:		Line 322:
	\|}		\|}

	The input string ''aaabcacc'' is, after 13 steps, split into ~~three~~ tokens: '''T1''' (corresponding to lexeme ''aaa''), '''T3''' (''bc''), '''T1''' (''c''), '''T1''' (''c'').		The input string ''aaabcacc'' is, after 13 steps, split into five tokens: '''T1''' (corresponding to lexeme ''aaa''), '''T3''' (''bc''), '''T1''' (''a''), '''T1''' (''c''), '''T1''' (''c'').

	[[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, c }...

2010-04-22T18:32:32Z

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, c }...

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, c }. Indicate the number of processing steps for the given input string.
* <nowiki>G = { a*|c, a|b*, bc* }</nowiki>, input string = aaabcacc

== NFA ==

The following is the result of applying Thompson's algorithm. State '''8''' recognizes the first expression (token '''T1'''); state '''16''' recognizes token '''T2'''; and state '''21''' 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 16 21
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
6 -> 7 [label="c",fontsize=10]
7 -> 8
5 -> 8

0 -> 9
9 -> 10
9 -> 12
10 -> 11 [label="a",fontsize=10]
12 -> 13
12 -> 15
13 -> 14 [label="b",fontsize=10]
14 -> 13
14 -> 15
15 -> 16
11 -> 16

0 -> 17
17 -> 18 [label="b",fontsize=10]
18 -> 19
18 -> 21
19 -> 20 [label="c",fontsize=10]
20 -> 19
20 -> 21

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, 15, '''16''', 17
! 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
! style="font-weight: normal; align: left; background: #e6e6e6;" | 3, 4, 5, '''8''', 11, '''16'''
! 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;" | 14, 18
! style="font-weight: normal; align: left; background: #e6e6e6;" | 13, 14, 15, '''16''', 18, 19, '''21'''
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''2''' (T2)
|-
! style="font-weight: normal; align: center; background: #e6e6e6;" | 0
! style="font-weight: normal; align: center; background: #e6e6e6;" | c
! style="font-weight: normal; align: center; background: #e6e6e6;" | 7
! style="font-weight: normal; align: left; background: #e6e6e6;" | 7, '''8'''
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''3''' (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
! style="font-weight: normal; align: left; background: #ffffcc;" | 3, 4, 5, '''8'''
! style="font-weight: normal; align: center; background: #ffffcc;" | '''4''' (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: #ffffcc;" | 1
! style="font-weight: normal; align: center; background: #ffffcc;" | c
! 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;" | 14
! style="font-weight: normal; align: left; background: #e6e6e6;" | 13, 14, 15, '''16'''
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''5''' (T2)
|-
! style="font-weight: normal; align: center; background: #e6e6e6;" | 2
! style="font-weight: normal; align: center; background: #e6e6e6;" | c
! style="font-weight: normal; align: center; background: #e6e6e6;" | 20
! style="font-weight: normal; align: left; background: #e6e6e6;" | 19, 20, '''21'''
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''6''' (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;" | -
! style="font-weight: normal; align: left; background: #ffffcc;" | -
! 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;" | 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: #ffffcc;" | 3
! style="font-weight: normal; align: center; background: #ffffcc;" | c
! 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;" | 4
! style="font-weight: normal; align: left; background: #e6e6e6;" | 3, 4, 5, '''8'''
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''4''' (T1)
|-
! 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;" | -
! 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;" | c
! 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: #ffffcc;" | 5
! style="font-weight: normal; align: center; background: #ffffcc;" | a
! 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: #ffffcc;" | 5
! style="font-weight: normal; align: center; background: #ffffcc;" | b
! style="font-weight: normal; align: center; background: #ffffcc;" | 4
! style="font-weight: normal; align: left; background: #ffffcc;" | 3, 4, 5, '''8'''
! style="font-weight: normal; align: center; background: #ffffcc;" | '''4''' (T1)
|-
! style="font-weight: normal; align: center; background: #ffffcc;" | 5
! style="font-weight: normal; align: center; background: #ffffcc;" | c
! 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;" | 6
! 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;" | 6
! style="font-weight: normal; align: center; background: #e6e6e6;" | b
! 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;" | 6
! style="font-weight: normal; align: center; background: #e6e6e6;" | c
! style="font-weight: normal; align: center; background: #e6e6e6;" | 20
! style="font-weight: normal; align: left; background: #e6e6e6;" | 19, 20, '''21'''
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''6''' (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 5 6
node [shape=circle,fixedsize=true,width=0.2,fontsize=10];
s -> 0
0 -> 1 [label="a",fontsize=10]
0 -> 2 [label="b",fontsize=10]
0 -> 3 [label="c",fontsize=10]
1 -> 4 [label="a",fontsize=10]
2 -> 5 [label="b",fontsize=10]
2 -> 6 [label="c",fontsize=10]
4 -> 4 [label="a",fontsize=10]
5 -> 5 [label="b",fontsize=10]
6 -> 6 [label="c",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, 5, 6}" -> "{} " [label="NF",fontsize=10]
"{0, 1, 2, 3, 4, 5, 6}" -> "{0, 1, 2, 3, 4, 5, 6} " [label=" F",fontsize=10]
"{0, 1, 2, 3, 4, 5, 6} " -> "{0, 1, 3, 4}" [label=" T1",fontsize=10]
"{0, 1, 2, 3, 4, 5, 6} " -> "{2, 5}" [label=" T2",fontsize=10]
"{0, 1, 2, 3, 4, 5, 6} " -> "{6}" [label=" T3",fontsize=10]
"{0, 1, 3, 4}" -> "{0, 1, 4}" [label=" a",fontsize=10]
"{0, 1, 3, 4}" -> "{3}" //[label=" a",fontsize=10]
"{2, 5}" -> "{2}" [label=" c",fontsize=10]
"{2, 5}" -> "{5}" //[label=" c",fontsize=10]
"{0, 1, 4}" -> "{0}" [label=" b",fontsize=10]
"{0, 1, 4}" -> "{1, 4}" //[label=" b",fontsize=10]
"{1, 4}" -> "{1, 4} " [label=" a, b, c",fontsize=10]
fontsize=10
//label="Minimization tree"
}
</graph>

Given the minimization tree, the final minimal DFA is 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 14 2 3 5 6
node [shape=circle,fixedsize=true,width=0.2,fontsize=10];
s -> 0
0 -> 14 [label="a",fontsize=10]
0 -> 2 [label="b",fontsize=10]
0 -> 3 [label="c",fontsize=10]
14 -> 14 [label="a",fontsize=10]
2 -> 5 [label="b",fontsize=10]
2 -> 6 [label="c",fontsize=10]
5 -> 5 [label="b",fontsize=10]
6 -> 6 [label="c",fontsize=10]
fontsize=10
}
</graph>

== Input Analysis ==

{| cellspacing="2"
! style="padding-left: 20px; padding-right: 20px; background: wheat;" | In
! style="padding-left: 20px; padding-right: 20px; background: wheat;" | Input
! style="padding-left: 20px; padding-right: 20px; background: wheat;" | In+1 / Token
|-
! style="font-weight: normal; align: center; background: #ffffcc;" | 0
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>aaabcacc$</tt>
! style="font-weight: normal; align: center; background: #ffffcc;" | 14
|-
! style="font-weight: normal; align: center; background: #ffffcc;" | 14
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>aabcacc$</tt>
! style="font-weight: normal; align: center; background: #ffffcc;" | 14
|-
! style="font-weight: normal; align: center; background: #ffffcc;" | 14
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>abcacc$</tt>
! style="font-weight: normal; align: center; background: #ffffcc;" | 14
|-
! style="font-weight: normal; align: center; background: #ffffcc;" | 14
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>bcacc$</tt>
! style="font-weight: normal; align: center; background: #ffffcc;" | '''T1''' (aaa)
|-
! style="font-weight: normal; align: center; background: #e6e6e6;" | 0
! style="font-weight: normal; text-align: right; background: #e6e6e6;" | <tt>bcacc$</tt>
! style="font-weight: normal; align: center; background: #e6e6e6;" | 2
|-
! style="font-weight: normal; align: center; background: #e6e6e6;" | 2
! style="font-weight: normal; text-align: right; background: #e6e6e6;" | <tt>cacc$</tt>
! style="font-weight: normal; align: center; background: #e6e6e6;" | 6
|-
! style="font-weight: normal; align: center; background: #e6e6e6;" | 6
! style="font-weight: normal; text-align: right; background: #e6e6e6;" | <tt>acc$</tt>
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''T3''' (bc)
|-
! style="font-weight: normal; align: center; background: #ffffcc;" | 0
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>acc$</tt>
! style="font-weight: normal; align: center; background: #ffffcc;" | 14
|-
! style="font-weight: normal; align: center; background: #ffffcc;" | 14
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>cc$</tt>
! style="font-weight: normal; align: center; background: #ffffcc;" | '''T1''' (a)
|-
! style="font-weight: normal; align: center; background: #e6e6e6;" | 0
! style="font-weight: normal; text-align: right; background: #e6e6e6;" | <tt>cc$</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>c$</tt>
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''T1''' (c)
|-
! style="font-weight: normal; align: center; background: #ffffcc;" | 0
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>c$</tt>
! style="font-weight: normal; align: center; background: #ffffcc;" | 3
|-
! style="font-weight: normal; align: center; background: #ffffcc;" | 3
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>$</tt>
! style="font-weight: normal; align: center; background: #ffffcc;" | '''T1''' (c)
|-
|}

The input string ''aaabcacc'' is, after 13 steps, split into three tokens: '''T1''' (corresponding to lexeme ''aaa''), '''T3''' (''bc''), '''T1''' (''c''), '''T1''' (''c'').

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