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

From Wiki**3

< Theoretical Aspects of Lexical Analysis
Root (talk | contribs)
PRIVATE, Bureaucrats, Administrators
15,362 edits
New page: __NOTOC__ Compute the non-deterministic finite automaton (NFA) by using Thompson's algorithm. Compute the minimal deterministic finite automaton (DFA).<br/>The alphabet is Σ = { a, b }. I...
 
Root (talk | contribs)
PRIVATE, Bureaucrats, Administrators
15,362 edits
No edit summary
 
(4 intermediate revisions by the same user not shown)
Line 5: Line 5:
== NFA ==
== NFA ==


The following is the result of applying Thompson's algorithm. State '''4''' 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 '''13''' recognizes token '''T2'''; and state '''17''' recognizes token '''T3'''.


<graph>
<kroki lang="graphviz">
digraph nfa {
digraph nfa {
     { node [shape=circle style=invis] s }
     { node [shape=circle style=invis] s }
Line 39: Line 39:
   14 -> 15
   14 -> 15
   14 -> 17
   14 -> 17
   15 -> 16 [label="a",fontsize=10]
   15 -> 16 [label="b",fontsize=10]
   16 -> 15
   16 -> 15
   16 -> 17
   16 -> 17
   fontsize=10
   fontsize=10
}
}
</graph>
</kroki>


== DFA ==
== DFA ==


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 60: Line 60:
! 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, 2, '''4''', 5, 6, 7, 9, 10, '''12''', 13, 14, 16, 17, 19, '''20'''
! style="font-weight: normal; align: left;  background: #ffffcc;" | 0, 1, 2, 3, 5, 6, '''8''', 9, 14, 15, '''17'''
! style="font-weight: normal; align: center; background: #ffffcc;" | '''0''' (T1)
! 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;" | 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;" | 3, 8, 15
! style="font-weight: normal; align: center; background: #e6e6e6;" | 4
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 2, 3, '''4''', 7, 8, 9, '''12''', 15, '''20'''
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 3, 4, 5, '''8'''
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''1''' (T1)
! 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;" | 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;" | 11, 18
! style="font-weight: normal; align: center; background: #e6e6e6;" | 7, 10, 16
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 11, '''12''', 17, 18, 19, '''20'''
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 7, '''8''', 10, 11, '''13''', 15, 16, '''17'''
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''2''' (T2)
! 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;" | 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;" | 3, 8
! style="font-weight: normal; align: center; background: #ffffcc;" | 4
! style="font-weight: normal; align: left;  background: #ffffcc;" | 2, 3, '''4''', 7, 8, 9, '''12'''
! style="font-weight: normal; align: left;  background: #ffffcc;" | 3, 4, 5, '''8'''
! style="font-weight: normal; align: center; background: #ffffcc;" | '''3''' (T1)
! style="font-weight: normal; align: center; background: #ffffcc;" | '''1''' (T1)
|-
|-
! style="font-weight: normal; align: center; background: #ffffcc;" | 1  
! style="font-weight: normal; align: center; background: #ffffcc;" | 1  
Line 89: Line 89:
! 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;" | a
! style="font-weight: normal; align: center; background: #e6e6e6;" | a
! style="font-weight: normal; align: center; background: #e6e6e6;" | -
! style="font-weight: normal; align: center; background: #e6e6e6;" | 12
! style="font-weight: normal; align: left;  background: #e6e6e6;" | -
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 11, 12, '''13'''
! style="font-weight: normal; align: center; background: #e6e6e6;" | -
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''3''' (T2)
|-
|-
! 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;" | 18
! style="font-weight: normal; align: center; background: #e6e6e6;" | 16
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 17, 18, 19, '''20'''
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 15, 16, '''17'''
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''4''' (T3)
! 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;" | 3
! 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;" | 3, 8
! style="font-weight: normal; align: center; background: #ffffcc;" | 12
! style="font-weight: normal; align: left;  background: #ffffcc;" | 2, 3, '''4''', 7, 8, 9, '''12'''
! style="font-weight: normal; align: left;  background: #ffffcc;" | 11, 12, '''13'''
! style="font-weight: normal; align: center; background: #ffffcc;" | '''3''' (T1)
! style="font-weight: normal; align: center; background: #ffffcc;" | '''3''' (T2)
|-
|-
! style="font-weight: normal; align: center; background: #ffffcc;" | 3
! style="font-weight: normal; align: center; background: #ffffcc;" | 3
Line 119: Line 119:
! 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;" | 18
! style="font-weight: normal; align: center; background: #e6e6e6;" | 16
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 17, 18, 19, '''20'''
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 15, 16, '''17'''
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''4''' (T3)
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''4''' (T3)
|}
|}
-->
 
Graphically, the DFA is represented as follows:
Graphically, the DFA is represented as follows:
<!--
 
<graph>
<kroki lang="graphviz">
digraph dfa {
digraph dfa {
     { node [shape=circle style=invis] s }
     { node [shape=circle style=invis] s }
Line 135: Line 135:
   0 -> 1 [label="a",fontsize=10]
   0 -> 1 [label="a",fontsize=10]
   0 -> 2 [label="b",fontsize=10]
   0 -> 2 [label="b",fontsize=10]
   1 -> 3 [label="a",fontsize=10]
   1 -> 1 [label="a",fontsize=10]
  2 -> 3 [label="a",fontsize=10]
   2 -> 4 [label="b",fontsize=10]
   2 -> 4 [label="b",fontsize=10]
   3 -> 3 [label="a",fontsize=10]
   3 -> 3 [label="a",fontsize=10]
Line 141: Line 142:
   fontsize=10
   fontsize=10
}
}
</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}" -> "{}" [label="NF",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, 4} " [label="  F",fontsize=10]
   "{0, 1, 2, 3, 4} " -> "{0, 1, 3}" [label="  T1",fontsize=10]
   "{0, 1, 2, 3, 4} " -> "{0, 1, 2}" [label="  T1",fontsize=10]
   "{0, 1, 2, 3, 4} " -> "{2}" [label="  T2",fontsize=10]
   "{0, 1, 2, 3, 4} " -> "{3}" [label="  T2",fontsize=10]
   "{0, 1, 2, 3, 4} " -> "{4}" [label="  T3",fontsize=10]
   "{0, 1, 2, 3, 4} " -> "{4}" [label="  T3",fontsize=10]
   "{0, 1, 3}" -> "{0}" [label="  b",fontsize=10]
   "{0, 1, 2}" -> "{0, 1}"
   "{0, 1, 3}" -> "{1,3}" //[label="  b",fontsize=10]
  "{0, 1, 2}" -> "{2}" [label="  a",fontsize=10]
   "{0, 1}" -> "{0}"
  "{0, 1}" -> "{1}" [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" 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}).
 
Given the minimization tree, the DFA is already minimal.


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 189: Line 175:
! 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>aababb$</tt>  
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>aababb$</tt>  
! 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; align: center; background: #ffffcc;" | 1
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>ababb$</tt>  
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>ababb$</tt>  
! 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; align: center; background: #ffffcc;" | 1
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>babb$</tt>  
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>babb$</tt>  
! style="font-weight: normal; align: center; background: #ffffcc;" | '''T1''' (aa)
! style="font-weight: normal; align: center; background: #ffffcc;" | '''T1''' (aa)
Line 205: Line 191:
! 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>abb$</tt>
! style="font-weight: normal; text-align: right; background: #e6e6e6;" | <tt>abb$</tt>
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''T2''' (b)
! 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>bb$</tt>
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''T2''' (ba)
|-
|-
! 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; align: center; background: #ffffcc;" | 13
|-
! 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;" | '''T1''' (a)
! style="font-weight: normal; align: center; background: #ffffcc;" | 2
|-
|-
! style="font-weight: normal; align: center; background: #e6e6e6;" | 0
! style="font-weight: normal; align: center; background: #ffffcc;" | 2
! style="font-weight: normal; text-align: right; background: #e6e6e6;" | <tt>bb$</tt>
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>b$</tt>
! 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; align: center; background: #ffffcc;" | 4
! style="font-weight: normal; text-align: right; background: #e6e6e6;" | <tt>b$</tt>
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>$</tt>
! style="font-weight: normal; align: center; background: #e6e6e6;" | 4
! style="font-weight: normal; align: center; background: #ffffcc;" | '''T3''' (bb)
|-
! 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 ''aababb'' is, after 10 steps, split into three tokens: '''T1''' (corresponding to lexeme ''aa''), '''T2''' (''b''), '''T1''' (''a''), and '''T3''' (''bb'').
The input string ''aababb'' is, after 9 steps, split into three tokens: '''T1''' (corresponding to lexeme ''aa''), '''T2''' (''ba''), and '''T3''' (''bb'').
-->
 
[[category:Teaching]]
[[category:Compiladores]]
[[category:Compilers]]
[[category:Ensino]]
[[en:Theoretical Aspects of Lexical Analysis]]
[[en:Theoretical Aspects of Lexical Analysis]]

Latest revision as of 18:45, 26 April 2026

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.

  • G = { a*|b, ba*, b* }, input string = aababb

NFA

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

DFA

Determination table for the above NFA:

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

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" transitions for super-state {0, 1}).

Given the minimization tree, the DFA is already minimal.

Input Analysis

In Input In+1 / Token
0 aababb$ 1
1 ababb$ 1
1 babb$ T1 (aa)
0 babb$ 2
2 abb$ 3
3 bb$ T2 (ba)
0 bb$ 2
2 b$ 4
4 $ T3 (bb)

The input string aababb is, after 9 steps, split into three tokens: T1 (corresponding to lexeme aa), T2 (ba), and T3 (bb).

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