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

From Wiki**3

< Theoretical Aspects of Lexical Analysis
← Older edit
Root (talk | contribs)
PRIVATE, Bureaucrats, Administrators
15,362 edits
No edit summary
Root (talk | contribs)
PRIVATE, Bureaucrats, Administrators
15,362 edits
No edit summary
 
(4 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 ====================== -->
== NFA ==
    </div>
 
  </div>
The following is the result of applying Thompson's algorithm.
  <div class="section">
 
    <p class="title" data-section-title>Solution</p>
<graph>
    <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:
<kroki lang="graphviz">
digraph nfa {
digraph nfa {
     { node [shape=circle style=invis] start }
     { node [shape=circle style=invis] start }
Line 23: Line 32:
   7 -> 1; 7 -> 8
   7 -> 1; 7 -> 8
   fontsize=10
   fontsize=10
  //label="NFA for ((ε|a)b)*"
}
}
</graph>
</kroki>
 
== DFA ==
 
Determination table for the above NFA:


Applying the determination algorithm to the above NFA, the following determination table is obtained:
{| 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 84: Line 89:
! style="text-align: left; font-weight:normal; vertical-align: top; width: 50%;" |Graphically, the DFA is represented as follows:
! style="text-align: left; font-weight:normal; vertical-align: top; width: 50%;" |Graphically, the DFA is represented as follows:


<graph>
<kroki lang="graphviz">
digraph dfa {
digraph dfa {
     { node [shape=circle style=invis] start }
     { node [shape=circle style=invis] start }
Line 97: Line 102:
   2 -> 2 [label="b"]
   2 -> 2 [label="b"]
   fontsize=10
   fontsize=10
  //label="DFA for ((ε|a)b)*"
}
}
</graph>
</kroki>


Given the minimization tree to the right, the final minimal DFA is:
Given the minimization tree to the right, the final minimal DFA is:
<graph>
<kroki lang="graphviz">
digraph dfamin {
digraph dfamin {
     { node [shape=circle style=invis] start }
     { node [shape=circle style=invis] start }
Line 113: Line 117:
   1 -> 02 [label="b"]
   1 -> 02 [label="b"]
   fontsize=10
   fontsize=10
  //label="DFA for (a|b)*"
}
}
</graph>
</kroki>


! 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.
! style="text-align: left; font-weight:normal; vertical-align: top; width: 50%;" | The minimization tree is as follows.


<graph>
<kroki lang="graphviz">
digraph mintree {  
digraph mintree {  
   node [shape=none,fixedsize=true,width=0.2,fontsize=10]
   node [shape=none,fixedsize=true,width=0.2,fontsize=10]
Line 126: Line 129:
   "{0, 2}" -> "{0,2} " [label="  a,b",fontsize=10]
   "{0, 2}" -> "{0,2} " [label="  a,b",fontsize=10]
   fontsize=10
   fontsize=10
  //label="Minimization tree"
}
}
</graph>
</kroki>
|}
|}
<!-- ====================== END OF SOLUTION ====================== -->
    </div>
  </div>
</div>
[[category:Compiladores]]
[[category:Ensino]]


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

Latest revision as of 18:24, 26 April 2026

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://robots.hlt.inesc-id.pt/w/pt/index.php?title=Theoretical_Aspects_of_Lexical_Analysis/Exercise_3&oldid=17694"