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

From Wiki**3

< Theoretical Aspects of Lexical Analysis
(→‎Solution)
(→‎Solution)
Line 53: Line 53:
  
 
{{CollapsedCode|Determination table|
 
{{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>
 
<table border="1" cellspacing="0"><colgroup span="3" width="84"></colgroup> <colgroup width="237"></colgroup> <colgroup width="84"></colgroup>
 
<tbody>
 
<tbody>
−
<tr style="height: 44px;">
+
<tr>
−
<td style="height: 44px;" align="center" bgcolor="#FFCC99"><strong><span style="font-family: Arial;">In</span></strong></td>
+
<td align="center" bgcolor="#FFCC99" height="44"><strong><span style="font-family: Arial;">In</span></strong></td>
−
<td style="height: 44px;" 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;">&alpha;&isin;&Sigma;</span></strong></td>
−
<td style="height: 44px;" 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;">move(In, &alpha;)</span></strong></td>
−
<td style="height: 44px;" 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;">&epsilon;-closure(move(In, &alpha;))</span></strong></td>
−
<td style="height: 44px;" align="center" bgcolor="#FFCC99"><strong><span style="font-family: Arial;">In+1&nbsp;= &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>
−
<tr style="height: 17px;">
+
<tr>
−
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">-</span></strong></td>
+
<td align="center" bgcolor="#FFFFCC" height="17"><strong><span style="font-family: Arial;">-</span></strong></td>
−
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">-</span></strong></td>
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">-</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">0</span></strong></td>
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">0</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">0, 1, 2, 4, 7</span></strong></td>
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">0, 1, 2, 4, 7</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">0</span></strong></td>
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">0</span></td>
 
</tr>
 
</tr>
−
<tr style="height: 17px;">
+
<tr>
−
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">0</span></strong></td>
+
<td align="center" bgcolor="#F5F5F5" height="17"><span style="font-family: Arial;">0</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">a</span></strong></td>
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">a</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">3, 8</span></strong></td>
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">3, 8</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">1, 2, 3, 4, 6, 7, 8</span></strong></td>
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">1, 2, 3, 4, 6, 7, 8</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">1</span></strong></td>
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">1</span></td>
 
</tr>
 
</tr>
−
<tr style="height: 17px;">
+
<tr>
−
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">0</span></strong></td>
+
<td align="center" bgcolor="#F5F5F5" height="17"><span style="font-family: Arial;">0</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">b</span></strong></td>
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">b</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">5</span></strong></td>
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">5</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">1, 2, 4, 5, 6, 7</span></strong></td>
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">1, 2, 4, 5, 6, 7</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">2</span></strong></td>
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">2</span></td>
 
</tr>
 
</tr>
−
<tr style="height: 17px;">
+
<tr>
−
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">1</span></strong></td>
+
<td align="center" bgcolor="#FFFFCC" height="17"><span style="font-family: Arial;">1</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">a</span></strong></td>
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">a</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">3, 8</span></strong></td>
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">3, 8</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">1, 2, 3, 4, 6, 7, 8</span></strong></td>
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">1, 2, 3, 4, 6, 7, 8</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">1</span></strong></td>
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">1</span></td>
 
</tr>
 
</tr>
−
<tr style="height: 17px;">
+
<tr>
−
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">1</span></strong></td>
+
<td align="center" bgcolor="#FFFFCC" height="17"><span style="font-family: Arial;">1</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">b</span></strong></td>
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">b</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">5, 9</span></strong></td>
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">5, 9</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">1, 2, 4, 5, 6, 7, 9</span></strong></td>
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">1, 2, 4, 5, 6, 7, 9</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">3</span></strong></td>
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">3</span></td>
 
</tr>
 
</tr>
−
<tr style="height: 17px;">
+
<tr>
−
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">2</span></strong></td>
+
<td align="center" bgcolor="#F5F5F5" height="17"><span style="font-family: Arial;">2</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">a</span></strong></td>
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">a</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">3, 8</span></strong></td>
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">3, 8</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">1, 2, 3, 4, 6, 7, 8</span></strong></td>
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">1, 2, 3, 4, 6, 7, 8</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">1</span></strong></td>
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">1</span></td>
 
</tr>
 
</tr>
−
<tr style="height: 17px;">
+
<tr>
−
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">2</span></strong></td>
+
<td align="center" bgcolor="#F5F5F5" height="17"><span style="font-family: Arial;">2</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">b</span></strong></td>
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">b</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">5</span></strong></td>
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">5</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">1, 2, 4, 5, 6, 7</span></strong></td>
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">1, 2, 4, 5, 6, 7</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">2</span></strong></td>
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">2</span></td>
 
</tr>
 
</tr>
−
<tr style="height: 17px;">
+
<tr>
−
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">3</span></strong></td>
+
<td align="center" bgcolor="#FFFFCC" height="17"><span style="font-family: Arial;">3</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">a</span></strong></td>
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">a</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">3, 8</span></strong></td>
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">3, 8</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">1, 2, 3, 4, 6, 7, 8</span></strong></td>
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">1, 2, 3, 4, 6, 7, 8</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">1</span></strong></td>
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">1</span></td>
 
</tr>
 
</tr>
−
<tr style="height: 17px;">
+
<tr>
−
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">3</span></strong></td>
+
<td align="center" bgcolor="#FFFFCC" height="17"><span style="font-family: Arial;">3</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">b</span></strong></td>
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">b</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">5, 10</span></strong></td>
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">5, 10</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">1, 2, 4, 5, 6, 7, 10, 11, 12, 14,&nbsp;17</span></strong></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 style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">4</span></strong></td>
+
<td align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">4</span></strong></td>
 
</tr>
 
</tr>
−
<tr style="height: 17px;">
+
<tr>
−
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">4</span></strong></td>
+
<td align="center" bgcolor="#F5F5F5" height="17"><strong><span style="font-family: Arial;">4</span></strong></td>
−
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">a</span></strong></td>
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">a</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">3, 8, 13</span></strong></td>
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">3, 8, 13</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16,&nbsp;17</span></strong></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 style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">5</span></strong></td>
+
<td align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">5</span></strong></td>
 
</tr>
 
</tr>
−
<tr style="height: 17px;">
+
<tr>
−
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">4</span></strong></td>
+
<td align="center" bgcolor="#F5F5F5" height="17"><strong><span style="font-family: Arial;">4</span></strong></td>
−
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">b</span></strong></td>
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">b</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">5, 15</span></strong></td>
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">5, 15</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">1, 2, 4, 5, 6, 7, 11, 12, 14, 15, 16,&nbsp;17</span></strong></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 style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">6</span></strong></td>
+
<td align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">6</span></strong></td>
 
</tr>
 
</tr>
−
<tr style="height: 17px;">
+
<tr>
−
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">5</span></strong></td>
+
<td align="center" bgcolor="#FFFFCC" height="17"><strong><span style="font-family: Arial;">5</span></strong></td>
−
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">a</span></strong></td>
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">a</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">3, 8, 13</span></strong></td>
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">3, 8, 13</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16,&nbsp;17</span></strong></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 style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">5</span></strong></td>
+
<td align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">5</span></strong></td>
 
</tr>
 
</tr>
−
<tr style="height: 17px;">
+
<tr>
−
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">5</span></strong></td>
+
<td align="center" bgcolor="#FFFFCC" height="17"><strong><span style="font-family: Arial;">5</span></strong></td>
−
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">b</span></strong></td>
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">b</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">5, 9, 15</span></strong></td>
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">5, 9, 15</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">1, 2, 4, 5, 6, 7, 9, 11, 12, 14, 15, 16,&nbsp;17</span></strong></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 style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">7</span></strong></td>
+
<td align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">7</span></strong></td>
 
</tr>
 
</tr>
−
<tr style="height: 17px;">
+
<tr>
−
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">6</span></strong></td>
+
<td align="center" bgcolor="#F5F5F5" height="17"><strong><span style="font-family: Arial;">6</span></strong></td>
−
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">a</span></strong></td>
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">a</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">3, 8, 13</span></strong></td>
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">3, 8, 13</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16,&nbsp;17</span></strong></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 style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">5</span></strong></td>
+
<td align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">5</span></strong></td>
 
</tr>
 
</tr>
−
<tr style="height: 17px;">
+
<tr>
−
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">6</span></strong></td>
+
<td align="center" bgcolor="#F5F5F5" height="17"><strong><span style="font-family: Arial;">6</span></strong></td>
−
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">b</span></strong></td>
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">b</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">5, 15</span></strong></td>
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">5, 15</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">1, 2, 4, 5, 6, 7, 11, 12, 14, 15, 16,&nbsp;17</span></strong></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 style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">6</span></strong></td>
+
<td align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">6</span></strong></td>
 
</tr>
 
</tr>
−
<tr style="height: 17px;">
+
<tr>
−
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">7</span></strong></td>
+
<td align="center" bgcolor="#FFFFCC" height="17"><strong><span style="font-family: Arial;">7</span></strong></td>
−
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">a</span></strong></td>
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">a</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">3, 8, 13</span></strong></td>
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">3, 8, 13</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16,&nbsp;17</span></strong></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 style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">5</span></strong></td>
+
<td align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">5</span></strong></td>
 
</tr>
 
</tr>
−
<tr style="height: 17px;">
+
<tr>
−
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">7</span></strong></td>
+
<td align="center" bgcolor="#FFFFCC" height="17"><strong><span style="font-family: Arial;">7</span></strong></td>
−
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">b</span></strong></td>
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">b</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">5, 10, 15</span></strong></td>
+
<td align="center" bgcolor="#FFFFCC"><span style="font-family: Arial;">5, 10, 15</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">1, 2, 4, 5, 6, 7, 10, 11, 12, 14, 15, 16,&nbsp;17</span></strong></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 style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">8</span></strong></td>
+
<td align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">8</span></strong></td>
 
</tr>
 
</tr>
−
<tr style="height: 17px;">
+
<tr>
−
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">8</span></strong></td>
+
<td align="center" bgcolor="#F5F5F5" height="17"><strong><span style="font-family: Arial;">8</span></strong></td>
−
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">a</span></strong></td>
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">a</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">3, 8, 13</span></strong></td>
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">3, 8, 13</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16,&nbsp;17</span></strong></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 style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">5</span></strong></td>
+
<td align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">5</span></strong></td>
 
</tr>
 
</tr>
−
<tr style="height: 17px;">
+
<tr>
−
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">8</span></strong></td>
+
<td align="center" bgcolor="#F5F5F5" height="17"><strong><span style="font-family: Arial;">8</span></strong></td>
−
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">b</span></strong></td>
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">b</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">5, 15</span></strong></td>
+
<td align="center" bgcolor="#F5F5F5"><span style="font-family: Arial;">5, 15</span></td>
−
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">1, 2, 4, 5, 6, 7, 11, 12, 14, 15, 16,&nbsp;17</span></strong></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 style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">6</span></strong></td>
+
<td align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">6</span></strong></td>
 
</tr>
 
</tr>
 
</tbody>
 
</tbody>
 
</table>
 
</table>
 +
___EOF___;
 +
</runphp>
 
}}
 
}}
  

Revision as of 10:04, 24 June 2016

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=7688"