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

From Wiki**3

< Theoretical Aspects of Lexical Analysis
← Older editNewer edit →
Root (talk | contribs)
PRIVATE, Bureaucrats, Administrators
15,362 edits
Root (talk | contribs)
PRIVATE, Bureaucrats, Administrators
15,362 edits
No edit summary
Line 1: Line 1:
Use Thompson's algorithm to build the NFA for the following regular expression. Build the corresponding DFA and minimize it.
__NOTOC__
* <nowiki>(a|b)*abb(a|b)*</nowiki>
<div class="section-container auto" data-section>
 
  <div class="section">
== NFA ==
    <p class="title" data-section-title>Problem</p>
 
    <div class="content" data-section-content>
The following is the result of applying Thompson's algorithm.
<!-- ====================== START OF PROBLEM ====================== -->
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>'''
<!-- ====================== END OF PROBLEM ====================== -->
    </div>
  </div>
  <div class="section">
    <p class="title" data-section-title>Solution</p>
    <div class="content" data-section-content>
<!-- ====================== START OF SOLUTION ====================== -->
The non-deterministic finite automaton (NFA), built by applying Thompson's algorithm to the regular expression '''<nowiki>(a|b)*abb(a|b)*</nowiki>''' is the following:
<graph>
<graph>
digraph nfa {
digraph nfa {
Line 39: Line 49:
   16 -> 17
   16 -> 17
   10 -> 17
   10 -> 17


   fontsize=10
   fontsize=10
Line 46: Line 55:
</graph>
</graph>


== DFA ==
Applying the determination algorithm to the above NFA, the following determination table is obtained:
 
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 171: Line 177:
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''6'''
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''6'''
|}
|}


Graphically, the DFA is represented as follows:
Graphically, the DFA is represented as follows:
<graph>
<graph>
digraph dfa {
digraph dfa {
Line 204: Line 208:
}
}
</graph>
</graph>
== Minimal DFA  ==


The minimization tree is as follows.  
The minimization tree is as follows.  
<graph>
<graph>
digraph mintree {  
digraph mintree {  
Line 244: Line 245:
}
}
</graph>  
</graph>  
<!-- ====================== END OF SOLUTION ====================== -->
    </div>
  </div>
</div>


[[Category:Teaching]] [[Category:Compilers]] [[en:Theoretical Aspects of Lexical Analysis|en:Theoretical Aspects of Lexical Analysis]]
[[category:Teaching]]
[[category:Compilers]]
[[en:Theoretical Aspects of Lexical Analysis]]

Revision as of 18:41, 18 February 2015

Problem

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

The non-deterministic finite automaton (NFA), built by applying Thompson's algorithm to the regular expression (a|b)*abb(a|b)* is the following: <graph> digraph nfa { 

    { node [shape=circle style=invis] s }
 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];

 s -> 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>

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, 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, 9, 15 1, 2, 4, 5, 6, 7, 9, 11, 12, 14, 15, 16, 17 7
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
7 a 3, 8, 13 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16, 17 5
7 b 5, 10, 15 1, 2, 4, 5, 6, 7, 10, 11, 12, 14, 15, 16, 17 8
8 a 3, 8, 13 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16, 17 5
8 b 5, 15 1, 2, 4, 5, 6, 7, 11, 12, 14, 15, 16, 17 6

Graphically, the DFA is represented as follows: <graph> digraph dfa { 

    { node [shape=circle style=invis] s }
 rankdir=LR; ratio=0.5
 node [shape=doublecircle,fixedsize=true,width=0.2,fontsize=10]; 4 5 6 7 8
 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 -> 1  [label="a",fontsize=10]
 1 -> 3  [label="b",fontsize=10]
 2 -> 1 [label="a",fontsize=10]
 2 -> 2 [label="b",fontsize=10]
 3 -> 1 [label="a",fontsize=10]
 3 -> 4 [label="b",fontsize=10]
 4 -> 5 [label="a",fontsize=10]
 4 -> 6 [label="b",fontsize=10]
 5 -> 5 [label="a",fontsize=10]
 5 -> 7 [label="b",fontsize=10]
 6 -> 5 [label="a",fontsize=10]
 6 -> 6 [label="b",fontsize=10]
 7 -> 5 [label="a",fontsize=10]
 7 -> 8 [label="b",fontsize=10]
 8 -> 5 [label="a",fontsize=10]
 8 -> 6 [label="b",fontsize=10]
 fontsize=10
 //label="DFA for (a|b)*abb(a|b)*"

} </graph>

The minimization tree is as follows. <graph> digraph mintree { 

 node [shape=none,fixedsize=true,width=0.7,fontsize=10]
 "{0, 1, 2, 3, 4, 5, 6, 7, 8} " -> "{0, 1, 2, 3}" [label="NF",fontsize=10]
 "{0, 1, 2, 3, 4, 5, 6, 7, 8} " -> "{4, 5, 6, 7, 8}" [label="  F",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 both "a" or "b" transitions (remember that, at this stage, we assume that individual states -- i.e., the final states -- are all indistinguishable).

Given the minimization tree above, the final minimal DFA is: <graph> digraph dfamin { 

    { node [shape=circle style=invis] s }
 rankdir=LR; ratio=0.5
 node [shape=doublecircle,fixedsize=true,width=0.4,fontsize=10]; 45678
 node [shape=circle,fixedsize=true,width=0.3,fontsize=10];
 s -> 02
 02 -> 1 [label="a",fontsize=10]
 02 -> 02 [label="b",fontsize=10]
 1 -> 1  [label="a",fontsize=10]
 1 -> 3  [label="b",fontsize=10]
 3 -> 1 [label="a",fontsize=10]
 3 -> 45678 [label="b",fontsize=10]
 45678 -> 45678 [label="a",fontsize=10]
 45678 -> 45678 [label="b",fontsize=10]
 fontsize=10
 //label="DFA for (a|b)*abb(a|b)*"

} </graph>

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