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

From Wiki**3

< Theoretical Aspects of Lexical Analysis
(New page: Use Thompson's algorithm to build the NFA for the following regular expression. Build the corresponding DFA and minimize it. * <nowiki>(a|b)*abb(a|b)*</nowiki> == Solution == [[category...)
 
Line 3: Line 3:
  
 
== Solution ==
 
== Solution ==
 +
 +
=== NFA ===
 +
 +
The following is the result of applying Thompson's algorithm.
 +
 +
<graph>
 +
digraph nfa {
 +
    { node [shape=circle style=invis] start }
 +
  rankdir=LR; ratio=0.5
 +
  node [shape=doublecircle,fixedsize=true,width=0.2,fontsize=10]; 17
 +
  node [shape=circle,fixedsize=true,width=0.2,fontsize=10];
 +
 +
  start -> 0
 +
  0 -> 1
 +
  1 -> 2
 +
  1 -> 4
 +
  2 -> 3 [label="a",fontsize=10]
 +
  4 -> 5 [label="b",fontsize=10]
 +
  3 -> 6
 +
  5 -> 6
 +
  6 -> 1
 +
  6 -> 7
 +
  0 -> 7
 +
 +
  7 -> 8 [label="a",fontsize=10]
 +
  8 -> 9 [label="b",fontsize=10]
 +
  9 -> 10 [label="b",fontsize=10]
 +
 +
  10 -> 11
 +
  11 -> 12
 +
  11 -> 14
 +
  12 -> 13 [label="a",fontsize=10]
 +
  14 -> 15 [label="b",fontsize=10]
 +
  13 -> 16
 +
  15 -> 16
 +
  16 -> 11
 +
  16 -> 17
 +
  10 -> 17
 +
 +
 +
  fontsize=10
 +
  //label="NFA for (a|b)*abb(a|b)*"
 +
}
 +
</graph>
 +
 +
=== 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, 7
 +
! style="font-weight: normal; align: center; background: #ffffcc;" | 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;" | 3, 8
 +
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 1, 2, 3, 4, 6, 7, 8
 +
! style="font-weight: normal; align: center; background: #e6e6e6;" | 1
 +
|-
 +
! 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;" | 5
 +
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 1, 2, 4, 5, 6, 7
 +
! style="font-weight: normal; align: center; background: #e6e6e6;" | 2
 +
|-
 +
! 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, 8
 +
! style="font-weight: normal; align: left;  background: #ffffcc;" | 1, 2, 3, 4, 6, 7, 8
 +
! 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;" | 5, 9
 +
! style="font-weight: normal; align: left;  background: #ffffcc;" | 1, 2, 4, 5, 6, 7, 9
 +
! style="font-weight: normal; align: center; background: #ffffcc;" | 3
 +
|-
 +
! 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;" | 3, 8
 +
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 1, 2, 3, 4, 6, 7, 8
 +
! style="font-weight: normal; align: center; background: #e6e6e6;" | 1
 +
|-
 +
! 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;" | 5
 +
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 1, 2, 4, 5, 6, 7
 +
! style="font-weight: normal; align: center; background: #e6e6e6;" | 2
 +
|-
 +
! style="font-weight: normal; align: center; background: #e6e6e6;" | 3
 +
! style="font-weight: normal; align: center; background: #e6e6e6;" | a
 +
! style="font-weight: normal; align: center; background: #e6e6e6;" | 3, 8
 +
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 1, 2, 3, 4, 6, 7, 8
 +
! style="font-weight: normal; align: center; background: #e6e6e6;" | 1
 +
|-
 +
! style="font-weight: normal; align: center; background: #e6e6e6;" | 3
 +
! style="font-weight: normal; align: center; background: #e6e6e6;" | b
 +
! style="font-weight: normal; align: center; background: #e6e6e6;" | 5, 10
 +
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 1, 2, 4, 5, 6, 7, 10, 11, 12, 14, '''17'''
 +
! 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;" | a
 +
! style="font-weight: normal; align: center; background: #e6e6e6;" | 3, 8, 13
 +
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16, '''17'''
 +
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''5'''
 +
|-
 +
! 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;" | 5, 15
 +
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 1, 2, 4, 5, 6, 7, 11, 12, 14, 15, 16, '''17'''
 +
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''6'''
 +
|-
 +
! style="font-weight: normal; align: center; background: #e6e6e6;" | 5
 +
! style="font-weight: normal; align: center; background: #e6e6e6;" | a
 +
! style="font-weight: normal; align: center; background: #e6e6e6;" | 3, 8, 13
 +
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16, '''17'''
 +
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''5'''
 +
|-
 +
! style="font-weight: normal; align: center; background: #e6e6e6;" | 5
 +
! style="font-weight: normal; align: center; background: #e6e6e6;" | b
 +
! style="font-weight: normal; align: center; background: #e6e6e6;" | 5, 15
 +
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 1, 2, 4, 5, 6, 7, 11, 12, 14, 15, 16, '''17'''
 +
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''6'''
 +
|-
 +
! 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;" | 3, 8, 13
 +
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16, '''17'''
 +
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''5'''
 +
|-
 +
! 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;" | 5, 15
 +
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 1, 2, 4, 5, 6, 7, 11, 12, 14, 15, 16, '''17'''
 +
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''6'''
 +
|}
 +
 +
 +
{| width="100%"
 +
! style="text-align: left; font-weight:normal; vertical-align: top; width: 50%;" |Graphically, the DFA is represented as follows:
 +
 +
<graph>
 +
digraph dfa {
 +
    { node [shape=circle style=invis] start }
 +
  rankdir=LR; ratio=0.5
 +
  node [shape=doublecircle,fixedsize=true,width=0.2,fontsize=10]; 4 5 6
 +
  node [shape=circle,fixedsize=true,width=0.2,fontsize=10];
 +
  start -> 0
 +
  0 -> 1 [label="a"]
 +
  0 -> 2 [label="b"]
 +
  1 -> 1  [label="a"]
 +
  1 -> 3  [label="b"]
 +
  2 -> 1 [label="a"]
 +
  2 -> 2 [label="b"]
 +
  3 -> 1 [label="a"]
 +
  3 -> 4 [label="b"]
 +
  4 -> 5 [label="a"]
 +
  4 -> 6 [label="b"]
 +
  5 -> 5 [label="a"]
 +
  5 -> 6 [label="b"]
 +
  6 -> 5 [label="a"]
 +
  6 -> 6 [label="b"]
 +
  fontsize=10
 +
  //label="DFA for (a|b)*abb(a|b)*"
 +
}
 +
</graph>
 +
 +
Given the minimization tree to the right, the final minimal DFA is:
 +
<graph>
 +
digraph dfamin {
 +
    { node [shape=circle style=invis] start }
 +
  rankdir=LR; ratio=0.5
 +
  node [shape=doublecircle,fixedsize=true,width=0.4,fontsize=10]; 456
 +
  node [shape=circle,fixedsize=true,width=0.2,fontsize=10];
 +
  start -> 02
 +
  02 -> 1 [label="a"]
 +
  02 -> 02 [label="b"]
 +
  1 -> 1  [label="a"]
 +
  1 -> 3  [label="b"]
 +
  3 -> 1 [label="a"]
 +
  3 -> 456 [label="b"]
 +
  456 -> 456 [label="a"]
 +
  456 -> 456 [label="b"]
 +
  fontsize=10
 +
  //label="DFA for (a|b)*abb(a|b)*"
 +
}
 +
</graph>
 +
 +
! style="text-align: left; font-weight:normal; vertical-align: top; width: 50%;" | The minimization tree is as follows. As can be seen, the states are indistinguishable.
 +
 +
<graph>
 +
digraph mintree {
 +
  node [shape=none,fixedsize=true,width=0.3,fontsize=10]
 +
  "{0, 1, 2, 3, 4, 5, 6}" -> "{0, 1, 2, 3}" [label="NF",fontsize=10]
 +
  "{0, 1, 2, 3, 4, 5, 6}" -> "{4, 5, 6}" [label="  F",fontsize=10]
 +
  //"{0, 1, 2, 3}" -> "{0, 1, 2, 3} " [label="  a",fontsize=10]
 +
  "{0, 1, 2, 3}" ->  "{0, 1, 2}"
 +
  "{0, 1, 2, 3}" -> "{3} " [label="  b",fontsize=10]
 +
  "{0, 1, 2}" -> "{0, 2} "
 +
  "{0, 1, 2}" -> "{1} " [label="  b",fontsize=10]
 +
  fontsize=10
 +
  //label="Minimization tree"
 +
}
 +
</graph>
 +
 +
The tree expansion for non-splitting sets has been omitted for simplicity ("a" transition for non-final states and the {0, 2} "a" and "b" transitions. The final states are all indistinguishable, regarding either "a" or "b" transitions.
 +
|}
  
 
[[category:Teaching]]
 
[[category:Teaching]]
 
[[category:Compilers]]
 
[[category:Compilers]]
 
[[en:Theoretical Aspects of Lexical Analysis]]
 
[[en:Theoretical Aspects of Lexical Analysis]]

Revision as of 03:33, 22 March 2009

Use Thompson's algorithm to build the NFA for the following regular expression. Build the corresponding DFA and minimize it.

  • (a|b)*abb(a|b)*

Solution

NFA

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


DFA

Determination table for the above NFA:

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


Graphically, the DFA is represented as follows:


Given the minimization tree to the right, the final minimal DFA is:


The minimization tree is as follows. As can be seen, the states are indistinguishable.


The tree expansion for non-splitting sets has been omitted for simplicity ("a" transition for non-final states and the {0, 2} "a" and "b" transitions. The final states are all indistinguishable, regarding either "a" or "b" transitions.

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