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

From Wiki**3

< Theoretical Aspects of Lexical Analysis
(Created page 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 194: Line 194:
  
 
Graphically, the DFA is represented as follows:
 
Graphically, the DFA is represented as follows:
−
<!--
+
 
 
<graph>
 
<graph>
 
digraph dfa {
 
digraph dfa {
 
     { node [shape=circle style=invis] s }
 
     { node [shape=circle style=invis] s }
 
   rankdir=LR; ratio=0.5
 
   rankdir=LR; ratio=0.5
−
   node [shape=doublecircle,fixedsize=true,width=0.2,fontsize=10]; 0 1 2 3 4 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];
 
   node [shape=circle,fixedsize=true,width=0.2,fontsize=10];
 
   s -> 0
 
   s -> 0
 +
 
   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]
+
   0 -> 3 [label="c",fontsize=10]
−
   2 -> 4 [label="a",fontsize=10]
+
 
−
   2 -> 5 [label="b",fontsize=10]
+
   1 -> 4 [label="a",fontsize=10]
−
   3 -> 3 [label="a",fontsize=10]
+
   1 -> 5 [label="b",fontsize=10]
 +
   1 -> 3 [label="c",fontsize=10]
 +
 
 +
  2 -> 6 [label="c",fontsize=10]
 +
 
 +
  3 -> 4 [label="a",fontsize=10]
 +
  3 -> 3 [label="c",fontsize=10]
 +
 
 
   4 -> 4 [label="a",fontsize=10]
 
   4 -> 4 [label="a",fontsize=10]
 +
  4 -> 3 [label="c",fontsize=10]
 +
 
   5 -> 5 [label="b",fontsize=10]
 
   5 -> 5 [label="b",fontsize=10]
 +
 +
  6 -> 6 [label="c",fontsize=10]
 +
 
   fontsize=10
 
   fontsize=10
 
}
 
}
 
</graph>
 
</graph>
−
-->
+
 
 
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>
 
<graph>
 
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, 5}" -> "{}" [label="NF",fontsize=10]
+
   "{0, 1, 2, 3, 4, 5, 6}" -> "{}     " [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, 6}" -> "{0, 1, 2, 3, 4, 5, 6} " [label="  F",fontsize=10]
−
   "{0, 1, 2, 3, 4, 5} " -> "{0, 1, 3}" [label="  T1",fontsize=10]
+
   "{0, 1, 2, 3, 4, 5, 6} " -> "{1, 5}" [label="  T1",fontsize=10]
−
   "{0, 1, 2, 3, 4, 5} " -> "{2, 4}" [label="  T2",fontsize=10]
+
   "{0, 1, 2, 3, 4, 5, 6} " -> "{0, 3, 4}" [label="  T2",fontsize=10]
−
   "{0, 1, 2, 3, 4, 5} " -> "{5}" [label="  T3",fontsize=10]
+
   "{0, 1, 2, 3, 4, 5, 6} " -> "{2, 6}" [label="  T3",fontsize=10]
−
   "{0, 1, 3}" -> "{0}" //[label="  b",fontsize=10]
+
   "{1, 5}" -> "{1}" //[label="  a",fontsize=10]
−
   "{0, 1, 3}" -> "{1,3}" [label="  b",fontsize=10]
+
  "{1, 5}" -> "{5}" [label="  a",fontsize=10]
−
   "{2, 4}" -> "{2}" //[label="  b",fontsize=10]
+
  "{0, 3, 4}" -> "{0}" //[label="  a",fontsize=10]
−
   "{2, 4}" -> "{4}" [label="  b",fontsize=10]
+
   "{0, 3, 4}" -> "{3, 4}" [label="  a",fontsize=10]
 +
   "{3, 4}" -> "{3, 4} " [label="  a,b,c",fontsize=10]
 +
   "{2, 6}" -> "{2, 6} " [label="  a,b,c",fontsize=10]
 
   fontsize=10
 
   fontsize=10
 
   //label="Minimization tree"
 
   //label="Minimization tree"
 
}
 
}
 
</graph>
 
</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}).
 
  
 
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.
Line 241: Line 254:
 
     { node [shape=circle style=invis] s }
 
     { node [shape=circle style=invis] s }
 
   rankdir=LR; ratio=0.5
 
   rankdir=LR; ratio=0.5
−
   node [shape=doublecircle,fixedsize=true,width=0.2,fontsize=10]; 0 13 2 4 5
+
   node [shape=doublecircle,fixedsize=true,width=0.2,fontsize=10]; 0 1 26 34 5
 
   node [shape=circle,fixedsize=true,width=0.2,fontsize=10];
 
   node [shape=circle,fixedsize=true,width=0.2,fontsize=10];
 
   s -> 0
 
   s -> 0
−
   0 -> 13 [label="a",fontsize=10]
+
   0 -> 1 [label="a",fontsize=10]
−
   0 -> 2 [label="b",fontsize=10]
+
   0 -> 26 [label="b",fontsize=10]
−
   13 -> 13 [label="a",fontsize=10]
+
   0 -> 34 [label="c",fontsize=10]
−
   2 -> 4 [label="a",fontsize=10]
+
  1 -> 34 [label="a,c",fontsize=10]
−
   4 -> 4 [label="a",fontsize=10]
+
   1 -> 5 [label="b",fontsize=10]
−
   2 -> 5 [label="b",fontsize=10]
+
   26 -> 26 [label="c",fontsize=10]
 +
   34 -> 34 [label="a,c",fontsize=10]
 
   5 -> 5 [label="b",fontsize=10]
 
   5 -> 5 [label="b",fontsize=10]
 
   fontsize=10
 
   fontsize=10
 
}
 
}
 
</graph>
 
</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 263: Line 277:
 
|-
 
|-
 
! 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>abbcac$</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>bbcac$</tt>  
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 13
+
! style="font-weight: normal; align: center; background: #ffffcc;" | 5
 
|-
 
|-
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 13
+
! style="font-weight: normal; align: center; background: #ffffcc;" | 5
−
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>babb$</tt>  
+
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>bcac$</tt>
−
! style="font-weight: normal; align: center; background: #ffffcc;" | '''T1''' (aa)
+
! 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>cac$</tt>  
 +
! style="font-weight: normal; align: center; background: #ffffcc;" | '''T1''' (abb)
 
|-
 
|-
 
! 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>babb$</tt>
+
! style="font-weight: normal; text-align: right; background: #e6e6e6;" | <tt>cac$</tt>
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | 2
+
! style="font-weight: normal; align: center; background: #e6e6e6;" | 34
−
|-
 
−
! 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; align: center; background: #e6e6e6;" | 34
−
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>bb$</tt>
+
! style="font-weight: normal; text-align: right; background: #e6e6e6;" | <tt>ac$</tt>
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 2
+
! style="font-weight: normal; align: center; background: #e6e6e6;" | 34
 
|-
 
|-
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 2
+
! style="font-weight: normal; align: center; background: #e6e6e6;" | 34
−
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>b$</tt>
+
! style="font-weight: normal; text-align: right; background: #e6e6e6;" | <tt>c$</tt>
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 5
+
! style="font-weight: normal; align: center; background: #e6e6e6;" | 34
 
|-
 
|-
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 5
+
! style="font-weight: normal; align: center; background: #e6e6e6;" | 34
−
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>$</tt>
+
! style="font-weight: normal; text-align: right; background: #e6e6e6;" | <tt>$</tt>
−
! style="font-weight: normal; align: center; background: #ffffcc;" | '''T3''' (bb)
+
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''T2''' (cac)
 
|}
 
|}
  
−
The input string ''aababb'' is, after 9 steps, split into three tokens: '''T1''' (corresponding to lexeme ''aa''), '''T2''' (''ba''), and '''T3''' (''bb'').
+
The input string ''abbcac'' is, after 8 steps, split into two tokens: '''T1''' (corresponding to lexeme ''abb''), and '''T2''' (''cac'').
−
-->
 
  
 
[[category:Teaching]]
 
[[category:Teaching]]
 
[[category:Compilers]]
 
[[category:Compilers]]
 
[[en:Theoretical Aspects of Lexical Analysis]]
 
[[en:Theoretical Aspects of Lexical Analysis]]

Revision as of 21:28, 8 April 2013

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.

  • G = { ab*, (a|c)*, bc*}, input string = abbcac

NFA

The following is the result of applying Thompson's algorithm.

State 5 recognizes the first expression (token T1); state 13 recognizes token T2; and state 18 recognizes token T3.


DFA

Determination table for the above NFA:

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


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.


Input Analysis

In Input In+1 / Token
0 abbcac$ 1
1 bbcac$ 5
5 bcac$ 5
5 cac$ T1 (abb)
0 cac$ 34
34 ac$ 34
34 c$ 34
34 $ T2 (cac)

The input string abbcac is, after 8 steps, split into two tokens: T1 (corresponding to lexeme abb), and T2 (cac).

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