Difference between revisions of "Theoretical Aspects of Lexical Analysis/Exercise 17"

From Wiki**3

< Theoretical Aspects of Lexical Analysis
(Replaced content with "__NOTOC__ Compute the non-deterministic finite automaton (NFA) by using Thompson's algorithm. Compute the minimal deterministic finite automaton (DFA).<br/>The alphabet is...")
Line 3: Line 3:
 
* <nowiki>G = { a*, ba*, a*|b }</nowiki>, input string = aababb
 
* <nowiki>G = { a*, ba*, a*|b }</nowiki>, input string = aababb
  
−
== NFA ==
+
== Solution ==
  
−
The following is the result of applying Thompson's algorithm.
+
[[Image:asbasasob1.jpg]]
−
<!--
+
[[Image:asbasasob2.jpg]]
−
State '''4''' recognizes the first expression (token '''T1'''); state '''9''' recognizes token '''T2'''; and state '''17''' recognizes token '''T3'''.
 
−
 
 
−
<dot-hack>
 
−
digraph nfa {
 
−
    { node [shape=circle style=invis] s }
 
−
  rankdir=LR; ratio=0.5
 
−
  node [shape=doublecircle,fixedsize=true,width=0.2,fontsize=10]; 4 9 17
 
−
  node [shape=circle,fixedsize=true,width=0.2,fontsize=10];
 
−
 
 
−
  s -> 0
 
−
 
 
−
  0 -> 1
 
−
  1 -> 2
 
−
  1 -> 4
 
−
  2 -> 3 [label="a",fontsize=10]
 
−
  3 -> 2
 
−
  3 -> 4
 
−
 
 
−
  0 -> 5
 
−
  5 -> 6 [label="b",fontsize=10]
 
−
  6 -> 7
 
−
  6 -> 9
 
−
  7 -> 8 [label="a",fontsize=10]
 
−
  8 -> 7
 
−
  8 -> 9
 
−
 
 
−
  0 -> 10
 
−
  10 -> 11
 
−
  10 -> 13
 
−
  11 -> 12 [label="a",fontsize=10]
 
−
  12 -> 17
 
−
  13 -> 14
 
−
  13 -> 16
 
−
  14 -> 15 [label="b",fontsize=10]
 
−
  15 -> 14
 
−
  15 -> 16
 
−
  16 -> 17
 
−
  fontsize=10
 
−
}
 
−
</dot-hack>
 
−
-->
 
−
== DFA ==
 
−
 
 
−
Determination table for the above NFA:
 
−
<!--
 
−
{| cellspacing="2"
 
−
! style="padding-left: 20px; padding-right: 20px; background: wheat;" | I<sub>n</sub>
 
−
! style="padding-left: 20px; padding-right: 20px; background: wheat;" | α∈Σ
 
−
! style="padding-left: 20px; padding-right: 20px; background: wheat;" | move(I<sub>n</sub>, α)
 
−
! style="padding-left: 20px; padding-right: 20px; background: wheat;" | ε-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;" | 0
 
−
! style="font-weight: normal; align: left;  background: #ffffcc;" | 0, 1, 2, '''4''', 5, 10, 11, 13, 14, 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;" | 3, 12
 
−
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 2, 3, '''4''', 12, '''17'''
 
−
! 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;" | 6, 15
 
−
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 6, 7, '''9''', 14, 15, 16, '''17'''
 
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''2''' (T2)
 
−
|-
 
−
! 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;" | 3
 
−
! style="font-weight: normal; align: left;  background: #ffffcc;" | 2, 3, '''4'''
 
−
! 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;" | 8
 
−
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 7, 8, '''9'''
 
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''4''' (T2)
 
−
|-
 
−
! 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;" | 15
 
−
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 14, 15, 16, '''17'''
 
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''5''' (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;" | 3
 
−
! style="font-weight: normal; align: left;  background: #ffffcc;" | 2, 3, '''4'''
 
−
! 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;" | 8
 
−
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 7, 8, '''9'''
 
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''4''' (T2)
 
−
|-
 
−
! 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: #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;" | 15
 
−
! style="font-weight: normal; align: left;  background: #ffffcc;" | 14, 15, 16, '''17'''
 
−
! style="font-weight: normal; align: center; background: #ffffcc;" | '''5''' (T3)
 
−
|}
 
−
-->
 
−
Graphically, the DFA is represented as follows:
 
−
<!--
 
−
<dot-hack>
 
−
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
 
−
  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="a",fontsize=10]
 
−
  2 -> 5 [label="b",fontsize=10]
 
−
  3 -> 3 [label="a",fontsize=10]
 
−
  4 -> 4 [label="a",fontsize=10]
 
−
  5 -> 5 [label="b",fontsize=10]
 
−
  fontsize=10
 
−
}
 
−
</dot-hack>
 
−
-->
 
−
The minimization tree is as follows. Note that before considering transition behavior, states are split according to the token they recognize.
 
−
<!--
 
−
<dot-hack>
 
−
digraph mintree {
 
−
  node [shape=none,fixedsize=true,width=0.3,fontsize=10]
 
−
  "{0, 1, 2, 3, 4, 5}" -> "{}" [label="NF",fontsize=10]
 
−
  "{0, 1, 2, 3, 4, 5}" -> "{0, 1, 2, 3, 4, 5} " [label="  F",fontsize=10]
 
−
  "{0, 1, 2, 3, 4, 5} " -> "{0, 1, 3}" [label="  T1",fontsize=10]
 
−
  "{0, 1, 2, 3, 4, 5} " -> "{2, 4}" [label="  T2",fontsize=10]
 
−
  "{0, 1, 2, 3, 4, 5} " -> "{5}" [label="  T3",fontsize=10]
 
−
  "{0, 1, 3}" -> "{0}"
 
−
  "{0, 1, 3}" -> "{1,3}" [label="  b",fontsize=10]
 
−
  "{2, 4}" -> "{2}"
 
−
  "{2, 4}" -> "{4}" [label="  b",fontsize=10]
 
−
  fontsize=10
 
−
}
 
−
</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.
 
−
 
 
−
<dot-hack>
 
−
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 5
 
−
  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="a",fontsize=10]
 
−
  4 -> 4 [label="a",fontsize=10]
 
−
  2 -> 5 [label="b",fontsize=10]
 
−
  5 -> 5 [label="b",fontsize=10]
 
−
  fontsize=10
 
−
}
 
−
</dot-hack>
 
−
-->
 
−
== Input Analysis ==
 
−
<!--
 
−
{| cellspacing="2"
 
−
! style="padding-left: 20px; padding-right: 20px; background: wheat;" | I<sub>n</sub>
 
−
! style="padding-left: 20px; padding-right: 20px; background: wheat;" | Input
 
−
! style="padding-left: 20px; padding-right: 20px; background: wheat;" | I<sub>n+1</sub> / Token
 
−
|-
 
−
! 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; align: center; background: #ffffcc;" | 13
 
−
|-
 
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 13
 
−
! 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;" | 13
 
−
! 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: #e6e6e6;" | 0
 
−
! style="font-weight: normal; text-align: right; background: #e6e6e6;" | <tt>babb$</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>abb$</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>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; text-align: right; background: #ffffcc;" | <tt>bb$</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>b$</tt>
 
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 5
 
−
|-
 
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 5
 
−
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>$</tt>
 
−
! style="font-weight: normal; align: center; background: #ffffcc;" | '''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:Compiladores]]
 
[[category:Compiladores]]

Revision as of 19:46, 23 April 2024

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*, ba*, a*|b }, input string = aababb

Solution

Asbasasob1.jpg Asbasasob2.jpg

Retrieved from "https://web.tecnico.ulisboa.pt/~david.matos/w/pt/index.php?title=Theoretical_Aspects_of_Lexical_Analysis/Exercise_17&oldid=16298"