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

From Wiki**3

< Theoretical Aspects of Lexical Analysis
(→‎Minimal DFA)
 
(12 intermediate revisions by the same user not shown)
Line 1: Line 1:
−
Use Thompson's algorithm to build the NFA for the following regular expression. Build the corresponding DFA and minimize it.
+
{{TOCright}}
−
* <nowiki>(a|b)*abb(a|b)*</nowiki>
 
  
−
== NFA ==
+
==Problem ==  
 +
Use Thompson's algorithm to build the NFA for the following regular expression. Build the corresponding DFA and minimize it.
  
−
The following is the result of applying Thompson's algorithm.
+
* '''<nowiki>(a|b)*abb(a|b)*</nowiki>'''
  
−
<graph>
+
== 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:
 +
{{CollapsedCode|NFA|
 +
<dot-hack>
 
digraph nfa {
 
digraph nfa {
 
     { node [shape=circle style=invis] s }
 
     { node [shape=circle style=invis] s }
Line 39: Line 43:
 
   16 -> 17
 
   16 -> 17
 
   10 -> 17
 
   10 -> 17
−
 
  
 
   fontsize=10
 
   fontsize=10
−
  //label="NFA for (a|b)*abb(a|b)*"
 
 
}
 
}
−
</graph>
+
</dot-hack>
 +
}}
  
−
== DFA ==
+
Applying the determination algorithm to the above NFA, the following determination table is obtained:
−
 
 
−
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: #ffffcc;" | 3
 
−
! 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;" | 3
 
−
! style="font-weight: normal; align: center; background: #ffffcc;" | b
 
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 5, 10
 
−
! style="font-weight: normal; align: left;  background: #ffffcc;" | 1, 2, 4, 5, 6, 7, 10, 11, 12, 14, '''17'''
 
−
! style="font-weight: normal; align: center; background: #ffffcc;" | '''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: #ffffcc;" | 5
 
−
! style="font-weight: normal; align: center; background: #ffffcc;" | a
 
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 3, 8, 13
 
−
! style="font-weight: normal; align: left;  background: #ffffcc;" | 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16, '''17'''
 
−
! style="font-weight: normal; align: center; background: #ffffcc;" | '''5'''
 
−
|-
 
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 5
 
−
! style="font-weight: normal; align: center; background: #ffffcc;" | b
 
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 5, 9, 15
 
−
! style="font-weight: normal; align: left;  background: #ffffcc;" | 1, 2, 4, 5, 6, 7, 9, 11, 12, 14, 15, 16, '''17'''
 
−
! style="font-weight: normal; align: center; background: #ffffcc;" | '''7'''
 
−
|-
 
−
! 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'''
 
−
|-
 
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 7
 
−
! style="font-weight: normal; align: center; background: #ffffcc;" | a
 
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 3, 8, 13
 
−
! style="font-weight: normal; align: left;  background: #ffffcc;" | 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16, '''17'''
 
−
! style="font-weight: normal; align: center; background: #ffffcc;" | '''5'''
 
−
|-
 
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 7
 
−
! style="font-weight: normal; align: center; background: #ffffcc;" | b
 
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 5, 10, 15
 
−
! style="font-weight: normal; align: left;  background: #ffffcc;" | 1, 2, 4, 5, 6, 7, 10, 11, 12, 14, 15, 16, '''17'''
 
−
! style="font-weight: normal; align: center; background: #ffffcc;" | '''8'''
 
−
|-
 
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | 8
 
−
! 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;" | 8
 
−
! 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'''
 
−
|}
 
  
 +
{{CollapsedCode|Determination table|
 +
<runphp>
 +
echo<<<___EOF___
 +
<table border="1" cellspacing="0"><colgroup span="3" width="84"></colgroup> <colgroup width="237"></colgroup> <colgroup width="84"></colgroup>
 +
<tbody>
 +
<tr>
 +
<td align="center" bgcolor="#FFCC99" height="44"><strong><span style="font-family: Arial;">In</span></strong></td>
 +
<td align="center" bgcolor="#FFCC99"><strong><span style="font-family: Arial;">&alpha;&isin;&Sigma;</span></strong></td>
 +
<td align="center" bgcolor="#FFCC99"><strong><span style="font-family: Arial;">move(In, &alpha;)</span></strong></td>
 +
<td align="center" bgcolor="#FFCC99"><strong><span style="font-family: Arial;">&epsilon;-closure(move(In, &alpha;))</span></strong></td>
 +
<td align="center" bgcolor="#FFCC99"><strong><span style="font-family: Arial;">In+1&nbsp;= &epsilon;-closure(move(In, &alpha;))</span></strong></td>
 +
</tr>
 +
<tr>
 +
<td align="center" bgcolor="#FFFFCC" height="17"><strong><span style="font-family: Arial;">-</span></strong></td>
 +
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">-</span></td>
 +
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">0</span></td>
 +
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">0, 1, 2, 4, 7</span></td>
 +
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">0</span></td>
 +
</tr>
 +
<tr>
 +
<td align="center" bgcolor="#F5F5F5" height="17"><span style="font-family: Arial;">0</span></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</span></td>
 +
<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>
 +
</tr>
 +
<tr>
 +
<td align="center" bgcolor="#F5F5F5" height="17"><span style="font-family: Arial;">0</span></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</span></td>
 +
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">1, 2, 4, 5, 6, 7</span></td>
 +
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">2</span></td>
 +
</tr>
 +
<tr>
 +
<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;">a</span></td>
 +
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">3, 8</span></td>
 +
<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>
 +
</tr>
 +
<tr>
 +
<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>
 +
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">5, 9</span></td>
 +
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">1, 2, 4, 5, 6, 7, 9</span></td>
 +
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">3</span></td>
 +
</tr>
 +
<tr>
 +
<td align="center" bgcolor="#F5F5F5" height="17"><span style="font-family: Arial;">2</span></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</span></td>
 +
<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>
 +
</tr>
 +
<tr>
 +
<td align="center" bgcolor="#F5F5F5" height="17"><span style="font-family: Arial;">2</span></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</span></td>
 +
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">1, 2, 4, 5, 6, 7</span></td>
 +
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">2</span></td>
 +
</tr>
 +
<tr>
 +
<td align="center" bgcolor="#FFFFCC" height="17"><span style="font-family: Arial;">3</span></td>
 +
<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>
 +
<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>
 +
</tr>
 +
<tr>
 +
<td align="center" bgcolor="#FFFFCC" height="17"><span style="font-family: Arial;">3</span></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</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>
 +
<td align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">4</span></strong></td>
 +
</tr>
 +
<tr>
 +
<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;">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;">4</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>
 +
<tr>
 +
<td align="center" bgcolor="#FFFFCC" height="17"><strong><span style="font-family: Arial;">5</span></strong></td>
 +
<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;">5</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, 9, 15</span></td>
 +
<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>
 +
<td align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">7</span></strong></td>
 +
</tr>
 +
<tr>
 +
<td align="center" bgcolor="#F5F5F5" height="17"><strong><span style="font-family: Arial;">6</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;">6</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>
 +
<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;">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 201: 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:
  
−
== Minimal DFA ==
+
{{CollapsedCode|Minimization tree|
 +
[[image:aula3p4mintree.jpg|350px]]
 +
}}
  
−
The minimization tree is as follows.
+
<!--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:
  
−
<graph>
+
{{CollapsedCode|Minimal DFA|
−
digraph mintree {  
+
<dot-hack>
−
  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 either "a" or "b" transitions.
 
−
 
 
−
Given the minimization tree above, the final minimal DFA is:
 
−
<graph>
 
 
digraph dfamin {
 
digraph dfamin {
 
     { node [shape=circle style=invis] s }
 
     { node [shape=circle style=invis] s }
 
   rankdir=LR; ratio=0.5
 
   rankdir=LR; ratio=0.5
−
   node [shape=doublecircle,fixedsize=true,width=0.4,fontsize=10]; 456
+
   node [shape=doublecircle,fixedsize=true,width=0.4,fontsize=10]; 45678
 
   node [shape=circle,fixedsize=true,width=0.3,fontsize=10];
 
   node [shape=circle,fixedsize=true,width=0.3,fontsize=10];
 
   s -> 02
 
   s -> 02
Line 238: Line 257:
 
   1 -> 3  [label="b",fontsize=10]
 
   1 -> 3  [label="b",fontsize=10]
 
   3 -> 1 [label="a",fontsize=10]
 
   3 -> 1 [label="a",fontsize=10]
−
   3 -> 456 [label="b",fontsize=10]
+
   3 -> 45678 [label="b",fontsize=10]
−
   456 -> 456 [label="a",fontsize=10]
+
   45678 -> 45678 [label="a",fontsize=10]
−
   456 -> 456 [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>  
 +
}}
 +
 
 +
[[category:Compiladores]]
 +
[[category:Ensino]]
  
−
[[category:Teaching]]
 
−
[[category:Compilers]]
 
 
[[en:Theoretical Aspects of Lexical Analysis]]
 
[[en:Theoretical Aspects of Lexical Analysis]]

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"