Theoretical Aspects of Lexical Analysis/Exercise 5: Difference between revisions

From Wiki**3

< Theoretical Aspects of Lexical Analysis
Root (talk | contribs)
PRIVATE, Bureaucrats, Administrators
15,362 edits
New page: 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 nu...
 
Root (talk | contribs)
PRIVATE, Bureaucrats, Administrators
15,362 edits
No edit summary
 
(162 intermediate revisions by the same user not shown)
Line 1: Line 1:
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.
__NOTOC__
* <nowiki>G = { ab, ab*, a|b }</nowiki>, input string = abaabb
Consider the lexical analyzer '''<nowiki>G = { ab, ab*, a|b }</nowiki>''', defined for the alphabet '''Σ = { a, b }'''.


== Solution ==
Compute the non-deterministic finite automaton (NFA) by using Thompson's algorithm. Compute the minimal deterministic finite automaton (DFA).


=== NFA ===
Indicate the number of processing steps for the '''abaabb''' input string.


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.
== NFA ==


<graph>
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'''.
 
<kroki lang="graphviz">
digraph nfa {
digraph nfa {
     { node [shape=circle style=invis] s }
     { node [shape=circle style=invis] s }
Line 37: Line 39:
   13 -> 14
   13 -> 14
   fontsize=10
   fontsize=10
  //label="NFA for (a|b)*abb(a|b)*"
}
}
</graph>
</kroki>


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


Determination table for the above NFA:
Applying the determination algorithm to the above NFA, the following determination table is obtained:


{| cellspacing="2"
{| cellspacing="2"
Line 52: Line 53:
! style="padding-left: 20px; padding-right: 20px; background: wheat;" | I<sub>n+1</sub> = ε-closure(move(I<sub>n</sub>, α))
! style="padding-left: 20px; padding-right: 20px; background: wheat;" | I<sub>n+1</sub> = ε-closure(move(I<sub>n</sub>, α))
|-
|-
! style="font-weight: normal; align: center; background: #ffffcc;" | -  
! style="font-weight: normal; align: center; background: #ffffcc;" | -
! 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: center; background: #ffffcc;" | 0
! style="font-weight: normal; align: left;  background: #ffffcc;" | 0, 1, 4, 9, 10, 12
! style="font-weight: normal; align: left;  background: #ffffcc;" | 0, 1, 4, 9, 10, 12
Line 59: Line 60:
|-
|-
! style="font-weight: normal; align: center; background: #e6e6e6;" | 0
! 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;" | a
! style="font-weight: normal; align: center; background: #e6e6e6;" | 2, 5, 11
! style="font-weight: normal; align: center; background: #e6e6e6;" | 2, 5, 11
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 2, 5, 6, '''8''', 11, '''14'''
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 2, 5, 6, '''8''', 11, '''14'''
Line 65: Line 66:
|-
|-
! style="font-weight: normal; align: center; background: #e6e6e6;" | 0
! 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;" | b
! style="font-weight: normal; align: center; background: #e6e6e6;" | 13
! style="font-weight: normal; align: center; background: #e6e6e6;" | 13
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 13, '''14'''
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 13, '''14'''
Line 71: Line 72:
|-
|-
! style="font-weight: normal; align: center; background: #ffffcc;" | 1
! 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;" | a
! style="font-weight: normal; align: center; background: #ffffcc;" | -
! style="font-weight: normal; align: center; background: #ffffcc;" | -
! style="font-weight: normal; align: left;  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;" | -
|-
|-
! style="font-weight: normal; align: center; background: #ffffcc;" | 1  
! 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;" | b
! style="font-weight: normal; align: center; background: #ffffcc;" | '''3''', 7
! style="font-weight: normal; align: center; background: #ffffcc;" | '''3''', 7
! style="font-weight: normal; align: left;  background: #ffffcc;" | '''3''', 6, 7, '''8'''
! style="font-weight: normal; align: left;  background: #ffffcc;" | '''3''', 6, 7, '''8'''
Line 89: Line 90:
|-
|-
! style="font-weight: normal; align: center; background: #e6e6e6;" | 2
! 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;" | b
! style="font-weight: normal; align: center; background: #e6e6e6;" | -
! style="font-weight: normal; align: center; background: #e6e6e6;" | -
! style="font-weight: normal; align: left;  background: #e6e6e6;" | -
! style="font-weight: normal; align: left;  background: #e6e6e6;" | -
Line 101: Line 102:
|-
|-
! style="font-weight: normal; align: center; background: #ffffcc;" | 3
! 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;" | b
! style="font-weight: normal; align: center; background: #ffffcc;" | 7
! style="font-weight: normal; align: center; background: #ffffcc;" | 7
! style="font-weight: normal; align: left;  background: #ffffcc;" | 6, 7, '''8'''
! style="font-weight: normal; align: left;  background: #ffffcc;" | 6, 7, '''8'''
Line 113: Line 114:
|-
|-
! style="font-weight: normal; align: center; background: #e6e6e6;" | 4
! 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;" | b
! style="font-weight: normal; align: center; background: #e6e6e6;" | 7
! style="font-weight: normal; align: center; background: #e6e6e6;" | 7
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 6, 7, '''8'''
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 6, 7, '''8'''
Line 119: Line 120:
|}
|}


 
Graphically, the DFA is represented as follows:
{| width="100%"
<kroki lang="graphviz">
! style="text-align: left; font-weight:normal; vertical-align: top; width: 50%;" |Graphically, the DFA is represented as follows:
 
<graph>
digraph dfa {
digraph dfa {
     { node [shape=circle style=invis] s }
     { node [shape=circle style=invis] s }
Line 133: Line 131:
   0 -> 2 [label="b",fontsize=10]
   0 -> 2 [label="b",fontsize=10]
   1 -> 3 [label="b",fontsize=10]
   1 -> 3 [label="b",fontsize=10]
  3 -> 1 [label="a",fontsize=10]
   3 -> 4 [label="b",fontsize=10]
   3 -> 4 [label="b",fontsize=10]
   4 -> 4 [label="b",fontsize=10]
   4 -> 4 [label="b",fontsize=10]
   fontsize=10
   fontsize=10
  //label="DFA for (a|b)*abb(a|b)*"
}
}
</graph>
</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.


<graph>
<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]
   "{0, 1, 2, 3, 4}" -> "{0}" [label="NF",fontsize=10]
   "{0, 1, 2, 3, 4}" -> "{0}" [label="NF",fontsize=10]
Line 151: Line 147:
   "{1, 2, 3, 4}" -> "{1, 4}" [label="  T2",fontsize=10]
   "{1, 2, 3, 4}" -> "{1, 4}" [label="  T2",fontsize=10]
   "{1, 2, 3, 4}" -> "{2}" [label="  T3",fontsize=10]
   "{1, 2, 3, 4}" -> "{2}" [label="  T3",fontsize=10]
   "{1, 4}" -> "{1}" //[label="  T3",fontsize=10]
   "{1, 4}" -> "{1}" /*[label="  T3",fontsize=10]*/
   "{1, 4}" -> "{4}" [label="  b",fontsize=10]
   "{1, 4}" -> "{4}" [label="  b",fontsize=10]
   fontsize=10
   fontsize=10
  //label="Minimization tree"
}
}
</graph>
</kroki>


The tree expansion for non-splitting sets has been omitted for simplicity ("a" transition for final states {1, 4}).
The tree expansion for non-splitting sets has been omitted for simplicity ("a" transition for final states {1, 4}).


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).
<!--
 
<graph>
== Input Analysis ==
digraph dfamin {
 
    { node [shape=circle style=invis] s }
{| cellspacing="2"
  rankdir=LR; ratio=0.5
! style="padding-left: 20px; padding-right: 20px; background: wheat;" | I<sub>n</sub>
  node [shape=doublecircle,fixedsize=true,width=0.4,fontsize=10]; 456
! style="padding-left: 20px; padding-right: 20px; background: wheat;" | Input
  node [shape=circle,fixedsize=true,width=0.3,fontsize=10];
! style="padding-left: 20px; padding-right: 20px; background: wheat;" | I<sub>n+1</sub> / Token
  s -> 02
|-
  02 -> 1 [label="a",fontsize=10]
! style="font-weight: normal; align: center; background: #ffffcc;" | 0
  02 -> 02 [label="b",fontsize=10]
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>abaabb$</tt>
  1 -> 1  [label="a",fontsize=10]
! style="font-weight: normal; align: center; background: #ffffcc;" | 1
  1 -> 3  [label="b",fontsize=10]
|-
  3 -> 1 [label="a",fontsize=10]
! style="font-weight: normal; align: center; background: #ffffcc;" | 1
  3 -> 456 [label="b",fontsize=10]
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>baabb$</tt>
  456 -> 456 [label="a",fontsize=10]
! style="font-weight: normal; align: center; background: #ffffcc;" | 3
  456 -> 456 [label="b",fontsize=10]
|-
  fontsize=10
! style="font-weight: normal; align: center; background: #ffffcc;" | 3
  //label="DFA for (a|b)*abb(a|b)*"
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>aabb$</tt>
}
! style="font-weight: normal; align: center; background: #ffffcc;" | '''T1'''
</graph>
|-
-->
! style="font-weight: normal; align: center; background: #e6e6e6;" | 0
! style="text-align: left; font-weight:normal; vertical-align: top; width: 50%;" |  
! style="font-weight: normal; text-align: right; background: #e6e6e6;" | <tt>aabb$</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>abb$</tt>
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''T2'''
|-
! 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; align: center; background: #ffffcc;" | 1
|-
! style="font-weight: normal; align: center; background: #ffffcc;" | 1
! 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;" | 3
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>b$</tt>
! style="font-weight: normal; align: center; background: #ffffcc;" | 4
|-
! style="font-weight: normal; align: center; background: #ffffcc;" | 4
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>$</tt>
! style="font-weight: normal; align: center; background: #ffffcc;" | '''T2'''
|}
|}


[[category:Teaching]]
The input string ''abaabb'' is, after 9 steps, split into three tokens: '''T1''' (corresponding to lexeme ''ab''), '''T2''' (''a''), and '''T2''' (''abb'').
[[category:Compilers]]
 
[[category:Compiladores]]
[[category:Ensino]]
 
[[en:Theoretical Aspects of Lexical Analysis]]
[[en:Theoretical Aspects of Lexical Analysis]]

Latest revision as of 18:39, 26 April 2026

Consider the lexical analyzer G = { ab, ab*, a|b }, defined for the alphabet Σ = { a, b }.

Compute the non-deterministic finite automaton (NFA) by using Thompson's algorithm. Compute the minimal deterministic finite automaton (DFA).

Indicate the number of processing steps for the abaabb input string.

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.

DFA

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

In α∈Σ move(In, α) ε-closure(move(In, α)) In+1 = ε-closure(move(In, α))
- - 0 0, 1, 4, 9, 10, 12 0
0 a 2, 5, 11 2, 5, 6, 8, 11, 14 1 (T2)
0 b 13 13, 14 2 (T3)
1 a - - -
1 b 3, 7 3, 6, 7, 8 3 (T1)
2 a - - -
2 b - - -
3 a - - -
3 b 7 6, 7, 8 4 (T2)
4 a - - -
4 b 7 6, 7, 8 4 (T2)

Graphically, the DFA is represented as follows:

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

The tree expansion for non-splitting sets has been omitted for simplicity ("a" transition for final states {1, 4}).

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

Input Analysis

In Input In+1 / Token
0 abaabb$ 1
1 baabb$ 3
3 aabb$ T1
0 aabb$ 1
1 abb$ T2
0 abb$ 1
1 bb$ 3
3 b$ 4
4 $ T2

The input string abaabb is, after 9 steps, split into three tokens: T1 (corresponding to lexeme ab), T2 (a), and T2 (abb).

Retrieved from "https://robots.hlt.inesc-id.pt/w/pt/index.php?title=Theoretical_Aspects_of_Lexical_Analysis/Exercise_5&oldid=17697"