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

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)*</nowiki>)
 
 
(7 intermediate revisions by the same user not shown)
Line 1: Line 1:
 +
__NOTOC__
 +
<div class="section-container auto" data-section>
 +
  <div class="section">
 +
    <p class="title" data-section-title>Problem</p>
 +
    <div class="content" data-section-content>
 +
<!-- ====================== START OF PROBLEM ====================== -->
 
Use Thompson's algorithm to build the NFA for the following regular expression. Build the corresponding DFA and minimize it.
 
Use Thompson's algorithm to build the NFA for the following regular expression. Build the corresponding DFA and minimize it.
  
−
* <nowiki>((ε|a)b)*</nowiki>
+
* '''<nowiki>((ε|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)*</nowiki>''' is the following:
 +
<dot-hack>
 +
digraph nfa {
 +
    { node [shape=circle style=invis] start }
 +
  rankdir=LR; ratio=0.5
 +
  node [shape=doublecircle,fixedsize=true,width=0.2,fontsize=10]; 8
 +
  node [shape=circle,fixedsize=true,width=0.2,fontsize=10];
 +
  start -> 0
 +
  0 -> 1; 0 -> 8
 +
  1 -> 2; 1 -> 4
 +
  2 -> 3;
 +
  3 -> 6
 +
  4 -> 5 [label="a",fontsize=10]
 +
  5 -> 6
 +
  6 -> 7 [label="b",fontsize=10]
 +
  7 -> 1; 7 -> 8
 +
  fontsize=10
 +
}
 +
</dot-hack>
 +
 
 +
Applying the determination algorithm to the above NFA, the following determination table is obtained:
 +
{| 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, 3, 4, 6, '''8'''
 +
! 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;" | 5
 +
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 5, 6
 +
! 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;" | 7
 +
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 1, 2, 3, 4, 6, 7, '''8'''
 +
! 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;" | -
 +
! style="font-weight: normal; align: left;  background: #ffffcc;" | -
 +
! style="font-weight: normal; align: center; background: #ffffcc;" | -
 +
|-
 +
! 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;" | 7
 +
! style="font-weight: normal; align: left;  background: #ffffcc;" | 1, 2, 3, 4, 6, 7, '''8'''
 +
! style="font-weight: normal; align: center; background: #ffffcc;" | '''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;" | 5
 +
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 5, 6
 +
! 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;" | 7
 +
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 1, 2, 3, 4, 6, 7, '''8'''
 +
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''2'''
 +
|}
 +
 
 +
{| width="100%"
 +
! style="text-align: left; font-weight:normal; vertical-align: top; width: 50%;" |Graphically, the DFA is represented as follows:
 +
 
 +
<dot-hack>
 +
digraph dfa {
 +
    { node [shape=circle style=invis] start }
 +
  rankdir=LR; ratio=0.5
 +
  node [shape=doublecircle,fixedsize=true,width=0.2,fontsize=10]; 0 2
 +
  node [shape=circle,fixedsize=true,width=0.2,fontsize=10];
 +
  start -> 0
 +
  0 -> 1 [label="a"]
 +
  0 -> 2 [label="b"]
 +
  1 -> 2  [label="b"]
 +
  2 -> 1 [label="a"]
 +
  2 -> 2 [label="b"]
 +
  fontsize=10
 +
}
 +
</dot-hack>
 +
 
 +
Given the minimization tree to the right, the final minimal DFA is:
 +
<dot-hack>
 +
digraph dfamin {
 +
    { node [shape=circle style=invis] start }
 +
  rankdir=LR; ratio=0.5
 +
  node [shape=doublecircle,fixedsize=true,width=0.3,fontsize=10]; 02
 +
  node [shape=circle,fixedsize=true,width=0.2,fontsize=10]; 1
 +
  start -> 02
 +
  02 -> 1 [label="a"]
 +
  02 -> 02 [label="b"]
 +
  1 -> 02 [label="b"]
 +
  fontsize=10
 +
}
 +
</dot-hack>
 +
 
 +
! style="text-align: left; font-weight:normal; vertical-align: top; width: 50%;" | The minimization tree is as follows.
 +
 
 +
<dot-hack>
 +
digraph mintree {
 +
  node [shape=none,fixedsize=true,width=0.2,fontsize=10]
 +
  "{0, 1, 2}" -> "{1}" [label="NF",fontsize=10]
 +
  "{0, 1, 2}" -> "{0, 2}" [label="  F",fontsize=10]
 +
  "{0, 2}" -> "{0,2} " [label="  a,b",fontsize=10]
 +
  fontsize=10
 +
}
 +
</dot-hack>
 +
|}
 +
<!-- ====================== END OF SOLUTION ====================== -->
 +
    </div>
 +
  </div>
 +
</div>
 +
 
 +
[[category:Compiladores]]
 +
[[category:Ensino]]
 +
 
 +
[[en:Theoretical Aspects of Lexical Analysis]]

Latest revision as of 22:42, 11 February 2019

Problem

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

  • ((ε|a)b)*

Solution

The non-deterministic finite automaton (NFA), built by applying Thompson's algorithm to the regular expression ((ε|a)b)* is the following:

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, 3, 4, 6, 8 0
0 a 5 5, 6 1
0 b 7 1, 2, 3, 4, 6, 7, 8 2
1 a - - -
1 b 7 1, 2, 3, 4, 6, 7, 8 2
2 a 5 5, 6 1
2 b 7 1, 2, 3, 4, 6, 7, 8 2
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.
Retrieved from "https://web.tecnico.ulisboa.pt/~david.matos/w/pt/index.php?title=Theoretical_Aspects_of_Lexical_Analysis/Exercise_3&oldid=11478"