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

From Wiki**3

< Theoretical Aspects of Lexical Analysis
 
(5 intermediate revisions by the same user not shown)
Line 1: Line 1:
−
__NOTOC__
+
{{TOCright}}
−
<div class="section-container auto" data-section>
+
 
−
  <div class="section">
+
==Problem ==  
−
    <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)*abb(a|b)*</nowiki>'''
 
* '''<nowiki>(a|b)*abb(a|b)*</nowiki>'''
−
<!-- ====================== END OF PROBLEM ====================== -->
+
 
−
    </div>
+
== Solution ==
−
  </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:
 
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>
+
{{CollapsedCode|NFA|
 +
<dot-hack>
 
digraph nfa {
 
digraph nfa {
 
     { node [shape=circle style=invis] s }
 
     { node [shape=circle style=invis] s }
Line 51: Line 45:
  
 
   fontsize=10
 
   fontsize=10
−
  //label="NFA for (a|b)*abb(a|b)*"
 
 
}
 
}
−
</graph>
+
</dot-hack>
 +
}}
  
 
Applying the determination algorithm to the above NFA, the following determination table is obtained:
 
Applying the determination algorithm to the above NFA, the following determination table is obtained:
  
−
{| cellspacing="2"
+
{{CollapsedCode|Determination table|
−
! style="padding-left: 20px; padding-right: 20px; background: wheat;" | I<sub>n</sub>
+
<runphp>
−
! style="padding-left: 20px; padding-right: 20px; background: wheat;" | α∈Σ
+
echo<<<___EOF___
−
! style="padding-left: 20px; padding-right: 20px; background: wheat;" | move(I<sub>n</sub>, α)
+
<table border="1" cellspacing="0"><colgroup span="3" width="84"></colgroup> <colgroup width="237"></colgroup> <colgroup width="84"></colgroup>
−
! style="padding-left: 20px; padding-right: 20px; background: wheat;" | ε-closure(move(I<sub>n</sub>, α))
+
<tbody>
−
! style="padding-left: 20px; padding-right: 20px; background: wheat;" | I<sub>n+1</sub> = ε-closure(move(I<sub>n</sub>, α))
+
<tr>
−
|-
+
<td align="center" bgcolor="#FFCC99" height="44"><strong><span style="font-family: Arial;">In</span></strong></td>
−
! style="font-weight: normal; align: center; background: #ffffcc;" | -
+
<td align="center" bgcolor="#FFCC99"><strong><span style="font-family: Arial;">&alpha;&isin;&Sigma;</span></strong></td>
−
! style="font-weight: normal; align: center; background: #ffffcc;" | -
+
<td align="center" bgcolor="#FFCC99"><strong><span style="font-family: Arial;">move(In, &alpha;)</span></strong></td>
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 0
+
<td align="center" bgcolor="#FFCC99"><strong><span style="font-family: Arial;">&epsilon;-closure(move(In, &alpha;))</span></strong></td>
−
! style="font-weight: normal; align: left;  background: #ffffcc;" | 0, 1, 2, 4, 7
+
<td align="center" bgcolor="#FFCC99"><strong><span style="font-family: Arial;">In+1&nbsp;= &epsilon;-closure(move(In, &alpha;))</span></strong></td>
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 0
+
</tr>
−
|-
+
<tr>
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | 0
+
<td align="center" bgcolor="#FFFFCC" height="17"><strong><span style="font-family: Arial;">-</span></strong></td>
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | a
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">-</span></td>
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | 3, 8
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">0</span></td>
−
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 1, 2, 3, 4, 6, 7, 8
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">0, 1, 2, 4, 7</span></td>
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | 1
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">0</span></td>
−
|-
+
</tr>
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | 0
+
<tr>
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | b
+
<td align="center" bgcolor="#F5F5F5" height="17"><span style="font-family: Arial;">0</span></td>
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | 5
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">a</span></td>
−
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 1, 2, 4, 5, 6, 7
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">3, 8</span></td>
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | 2
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">1, 2, 3, 4, 6, 7, 8</span></td>
−
|-
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">1</span></td>
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 1
+
</tr>
−
! style="font-weight: normal; align: center; background: #ffffcc;" | a
+
<tr>
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 3, 8
+
<td align="center" bgcolor="#F5F5F5" height="17"><span style="font-family: Arial;">0</span></td>
−
! style="font-weight: normal; align: left;  background: #ffffcc;" | 1, 2, 3, 4, 6, 7, 8
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">b</span></td>
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 1
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">5</span></td>
−
|-
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">1, 2, 4, 5, 6, 7</span></td>
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 1
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">2</span></td>
−
! style="font-weight: normal; align: center; background: #ffffcc;" | b
+
</tr>
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 5, 9
+
<tr>
−
! style="font-weight: normal; align: left;  background: #ffffcc;" | 1, 2, 4, 5, 6, 7, 9
+
<td align="center" bgcolor="#FFFFCC" height="17"><span style="font-family: Arial;">1</span></td>
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 3
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">a</span></td>
−
|-
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">3, 8</span></td>
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | 2
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">1, 2, 3, 4, 6, 7, 8</span></td>
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | a
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">1</span></td>
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | 3, 8
+
</tr>
−
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 1, 2, 3, 4, 6, 7, 8
+
<tr>
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | 1
+
<td align="center" bgcolor="#FFFFCC" height="17"><span style="font-family: Arial;">1</span></td>
−
|-
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">b</span></td>
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | 2
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">5, 9</span></td>
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | b
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">1, 2, 4, 5, 6, 7, 9</span></td>
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | 5
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">3</span></td>
−
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 1, 2, 4, 5, 6, 7
+
</tr>
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | 2
+
<tr>
−
|-
+
<td align="center" bgcolor="#F5F5F5" height="17"><span style="font-family: Arial;">2</span></td>
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 3
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">a</span></td>
−
! style="font-weight: normal; align: center; background: #ffffcc;" | a
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">3, 8</span></td>
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 3, 8
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">1, 2, 3, 4, 6, 7, 8</span></td>
−
! style="font-weight: normal; align: left;  background: #ffffcc;" | 1, 2, 3, 4, 6, 7, 8
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">1</span></td>
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 1
+
</tr>
−
|-
+
<tr>
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 3
+
<td align="center" bgcolor="#F5F5F5" height="17"><span style="font-family: Arial;">2</span></td>
−
! style="font-weight: normal; align: center; background: #ffffcc;" | b
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">b</span></td>
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 5, 10
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">5</span></td>
−
! style="font-weight: normal; align: left;  background: #ffffcc;" | 1, 2, 4, 5, 6, 7, 10, 11, 12, 14, '''17'''
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">1, 2, 4, 5, 6, 7</span></td>
−
! style="font-weight: normal; align: center; background: #ffffcc;" | '''4'''
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">2</span></td>
−
|-
+
</tr>
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | 4
+
<tr>
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | a
+
<td align="center" bgcolor="#FFFFCC" height="17"><span style="font-family: Arial;">3</span></td>
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | 3, 8, 13
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">a</span></td>
−
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16, '''17'''
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">3, 8</span></td>
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''5'''
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">1, 2, 3, 4, 6, 7, 8</span></td>
−
|-
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">1</span></td>
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | 4
+
</tr>
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | b
+
<tr>
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | 5, 15
+
<td align="center" bgcolor="#FFFFCC" height="17"><span style="font-family: Arial;">3</span></td>
−
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 1, 2, 4, 5, 6, 7, 11, 12, 14, 15, 16, '''17'''
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">b</span></td>
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''6'''
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">5, 10</span></td>
−
|-
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">1, 2, 4, 5, 6, 7, 10, 11, 12, 14,&nbsp;17</span></td>
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 5
+
<td align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">4</span></strong></td>
−
! style="font-weight: normal; align: center; background: #ffffcc;" | a
+
</tr>
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 3, 8, 13
+
<tr>
−
! style="font-weight: normal; align: left;  background: #ffffcc;" | 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16, '''17'''
+
<td align="center" bgcolor="#F5F5F5" height="17"><strong><span style="font-family: Arial;">4</span></strong></td>
−
! style="font-weight: normal; align: center; background: #ffffcc;" | '''5'''
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">a</span></td>
−
|-
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">3, 8, 13</span></td>
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 5
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16,&nbsp;17</span></td>
−
! style="font-weight: normal; align: center; background: #ffffcc;" | b
+
<td align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">5</span></strong></td>
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 5, 9, 15
+
</tr>
−
! style="font-weight: normal; align: left;  background: #ffffcc;" | 1, 2, 4, 5, 6, 7, 9, 11, 12, 14, 15, 16, '''17'''
+
<tr>
−
! style="font-weight: normal; align: center; background: #ffffcc;" | '''7'''
+
<td align="center" bgcolor="#F5F5F5" height="17"><strong><span style="font-family: Arial;">4</span></strong></td>
−
|-
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">b</span></td>
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | 6
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">5, 15</span></td>
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | a
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">1, 2, 4, 5, 6, 7, 11, 12, 14, 15, 16,&nbsp;17</span></td>
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | 3, 8, 13
+
<td align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">6</span></strong></td>
−
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16, '''17'''
+
</tr>
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''5'''
+
<tr>
−
|-
+
<td align="center" bgcolor="#FFFFCC" height="17"><strong><span style="font-family: Arial;">5</span></strong></td>
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | 6
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">a</span></td>
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | b
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">3, 8, 13</span></td>
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | 5, 15
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16,&nbsp;17</span></td>
−
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 1, 2, 4, 5, 6, 7, 11, 12, 14, 15, 16, '''17'''
+
<td align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">5</span></strong></td>
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''6'''
+
</tr>
−
|-
+
<tr>
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 7
+
<td align="center" bgcolor="#FFFFCC" height="17"><strong><span style="font-family: Arial;">5</span></strong></td>
−
! style="font-weight: normal; align: center; background: #ffffcc;" | a
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">b</span></td>
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 3, 8, 13
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">5, 9, 15</span></td>
−
! style="font-weight: normal; align: left;  background: #ffffcc;" | 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16, '''17'''
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">1, 2, 4, 5, 6, 7, 9, 11, 12, 14, 15, 16,&nbsp;17</span></td>
−
! style="font-weight: normal; align: center; background: #ffffcc;" | '''5'''
+
<td align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">7</span></strong></td>
−
|-
+
</tr>
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 7
+
<tr>
−
! style="font-weight: normal; align: center; background: #ffffcc;" | b
+
<td align="center" bgcolor="#F5F5F5" height="17"><strong><span style="font-family: Arial;">6</span></strong></td>
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 5, 10, 15
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">a</span></td>
−
! style="font-weight: normal; align: left;  background: #ffffcc;" | 1, 2, 4, 5, 6, 7, 10, 11, 12, 14, 15, 16, '''17'''
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">3, 8, 13</span></td>
−
! style="font-weight: normal; align: center; background: #ffffcc;" | '''8'''
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16,&nbsp;17</span></td>
−
|-
+
<td align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">5</span></strong></td>
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | 8
+
</tr>
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | a
+
<tr>
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | 3, 8, 13
+
<td align="center" bgcolor="#F5F5F5" height="17"><strong><span style="font-family: Arial;">6</span></strong></td>
−
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16, '''17'''
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">b</span></td>
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''5'''
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">5, 15</span></td>
−
|-
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">1, 2, 4, 5, 6, 7, 11, 12, 14, 15, 16,&nbsp;17</span></td>
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | 8
+
<td align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">6</span></strong></td>
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | b
+
</tr>
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | 5, 15
+
<tr>
−
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 1, 2, 4, 5, 6, 7, 11, 12, 14, 15, 16, '''17'''
+
<td align="center" bgcolor="#FFFFCC" height="17"><strong><span style="font-family: Arial;">7</span></strong></td>
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''6'''
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">a</span></td>
−
|}
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">3, 8, 13</span></td>
 +
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16,&nbsp;17</span></td>
 +
<td align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">5</span></strong></td>
 +
</tr>
 +
<tr>
 +
<td align="center" bgcolor="#FFFFCC" height="17"><strong><span style="font-family: Arial;">7</span></strong></td>
 +
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">b</span></td>
 +
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">5, 10, 15</span></td>
 +
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">1, 2, 4, 5, 6, 7, 10, 11, 12, 14, 15, 16,&nbsp;17</span></td>
 +
<td align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">8</span></strong></td>
 +
</tr>
 +
<tr>
 +
<td align="center" bgcolor="#F5F5F5" height="17"><strong><span style="font-family: Arial;">8</span></strong></td>
 +
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">a</span></td>
 +
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">3, 8, 13</span></td>
 +
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16,&nbsp;17</span></td>
 +
<td align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">5</span></strong></td>
 +
</tr>
 +
<tr>
 +
<td align="center" bgcolor="#F5F5F5" height="17"><strong><span style="font-family: Arial;">8</span></strong></td>
 +
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">b</span></td>
 +
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">5, 15</span></td>
 +
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">1, 2, 4, 5, 6, 7, 11, 12, 14, 15, 16,&nbsp;17</span></td>
 +
<td align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">6</span></strong></td>
 +
</tr>
 +
</tbody>
 +
</table>
 +
___EOF___;
 +
</runphp>
 +
}}
  
 
Graphically, the DFA is represented as follows:
 
Graphically, the DFA is represented as follows:
  
−
<graph>
+
{{CollapsedCode|DFA|
 +
<dot-hack>
 
digraph dfa {
 
digraph dfa {
 
     { node [shape=circle style=invis] s }
 
     { node [shape=circle style=invis] s }
Line 207: Line 231:
 
   8 -> 6 [label="b",fontsize=10]
 
   8 -> 6 [label="b",fontsize=10]
 
   fontsize=10
 
   fontsize=10
−
  //label="DFA for (a|b)*abb(a|b)*"
 
 
}
 
}
−
</graph>
+
</dot-hack>
−
 
+
}}
 
The minimization tree is as follows:
 
The minimization tree is as follows:
  
−
<graph>
+
{{CollapsedCode|Minimization tree|
−
digraph mintree {  
+
[[image:aula3p4mintree.jpg|350px]]
−
  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).
 
  
 +
<!--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 as follows:
 
Given the minimization tree above, the final minimal DFA is as follows:
  
−
<graph>
+
{{CollapsedCode|Minimal DFA|
 +
<dot-hack>
 
digraph dfamin {
 
digraph dfamin {
 
     { node [shape=circle style=invis] s }
 
     { node [shape=circle style=invis] s }
Line 247: Line 261:
 
   45678 -> 45678 [label="b",fontsize=10]
 
   45678 -> 45678 [label="b",fontsize=10]
 
   fontsize=10
 
   fontsize=10
−
  //label="DFA for (a|b)*abb(a|b)*"
 
 
}
 
}
−
</graph>
+
</dot-hack>  
−
<!-- ====================== END OF SOLUTION ====================== -->
+
}}
−
    </div>
 
−
  </div>
 
−
</div>
 
  
 
[[category:Compiladores]]
 
[[category:Compiladores]]

Latest revision as of 22:44, 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)*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:

NFA

Applying the determination algorithm to the above NFA, the following determination table is obtained:

Determination table
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:

DFA

The minimization tree is as follows:

Minimization tree

Aula3p4mintree.jpg

Given the minimization tree above, the final minimal DFA is as follows:

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