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

From Wiki**3

< Theoretical Aspects of Lexical Analysis
← Older edit
Root (talk | contribs)
PRIVATE, Bureaucrats, Administrators
15,362 edits
Root (talk | contribs)
PRIVATE, Bureaucrats, Administrators
15,362 edits
No edit summary
 
(3 intermediate revisions by the same user not shown)
Line 10: Line 10:
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:
{{CollapsedCode|NFA|
{{CollapsedCode|NFA|
<graph>
<kroki lang="graphviz">
digraph nfa {
digraph nfa {
     { node [shape=circle style=invis] s }
     { node [shape=circle style=invis] s }
Line 45: Line 45:


   fontsize=10
   fontsize=10
  //label="NFA for (a|b)*abb(a|b)*"
}
}
</graph>
</kroki>
}}
}}


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:


{{CollapsedCode|Determination table|
{| class="mw-collapsible mw-collapsed" border="1" cellspacing="0" style="font-family: Arial; text-align: center; border-collapse: collapse;"
<table border="1" cellspacing="0"><colgroup span="3" width="84"></colgroup> <colgroup width="237"></colgroup> <colgroup width="84"></colgroup>
|+ '''Determination table'''
<tbody>
|-
<tr style="height: 44px;">
! style="background-color:#FFCC99; height:44px; width:84px;" | '''In'''
<td style="height: 44px;" align="center" bgcolor="#FFCC99"><strong><span style="font-family: Arial;">In</span></strong></td>
! style="background-color:#FFCC99; width:84px;" | '''&alpha;&isin;&Sigma;'''
<td style="height: 44px;" align="center" bgcolor="#FFCC99"><strong><span style="font-family: Arial;">&alpha;&isin;&Sigma;</span></strong></td>
! style="background-color:#FFCC99; width:84px;" | '''move(In, &alpha;)'''
<td style="height: 44px;" align="center" bgcolor="#FFCC99"><strong><span style="font-family: Arial;">move(In, &alpha;)</span></strong></td>
! style="background-color:#FFCC99; width:237px;" | '''&epsilon;-closure(move(In, &alpha;))'''
<td style="height: 44px;" align="center" bgcolor="#FFCC99"><strong><span style="font-family: Arial;">&epsilon;-closure(move(In, &alpha;))</span></strong></td>
! style="background-color:#FFCC99; width:84px;" | '''In+1 = &epsilon;-closure(move(In, &alpha;))'''
<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>
|- style="background-color:#FFFFCC; height:17px;"
</tr>
| '''-''' || - || 0 || 0, 1, 2, 4, 7 || 0
<tr style="height: 17px;">
|- style="background-color:#F5F5F5; height:17px;"
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">-</span></strong></td>
| 0 || a || 3, 8 || 1, 2, 3, 4, 6, 7, 8 || 1
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">-</span></strong></td>
|- style="background-color:#F5F5F5; height:17px;"
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">0</span></strong></td>
| 0 || b || 5 || 1, 2, 4, 5, 6, 7 || 2
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">0, 1, 2, 4, 7</span></strong></td>
|- style="background-color:#FFFFCC; height:17px;"
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">0</span></strong></td>
| 1 || a || 3, 8 || 1, 2, 3, 4, 6, 7, 8 || 1
</tr>
|- style="background-color:#FFFFCC; height:17px;"
<tr style="height: 17px;">
| 1 || b || 5, 9 || 1, 2, 4, 5, 6, 7, 9 || 3
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">0</span></strong></td>
|- style="background-color:#F5F5F5; height:17px;"
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">a</span></strong></td>
| 2 || a || 3, 8 || 1, 2, 3, 4, 6, 7, 8 || 1
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">3, 8</span></strong></td>
|- style="background-color:#F5F5F5; height:17px;"
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">1, 2, 3, 4, 6, 7, 8</span></strong></td>
| 2 || b || 5 || 1, 2, 4, 5, 6, 7 || 2
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">1</span></strong></td>
|- style="background-color:#FFFFCC; height:17px;"
</tr>
| 3 || a || 3, 8 || 1, 2, 3, 4, 6, 7, 8 || 1
<tr style="height: 17px;">
|- style="background-color:#FFFFCC; height:17px;"
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">0</span></strong></td>
| 3 || b || 5, 10 || 1, 2, 4, 5, 6, 7, 10, 11, 12, 14,&nbsp;17 || '''4'''
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">b</span></strong></td>
|- style="background-color:#F5F5F5; height:17px;"
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">5</span></strong></td>
| '''4''' || a || 3, 8, 13 || 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16,&nbsp;17 || '''5'''
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">1, 2, 4, 5, 6, 7</span></strong></td>
|- style="background-color:#F5F5F5; height:17px;"
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">2</span></strong></td>
| '''4''' || b || 5, 15 || 1, 2, 4, 5, 6, 7, 11, 12, 14, 15, 16,&nbsp;17 || '''6'''
</tr>
|- style="background-color:#FFFFCC; height:17px;"
<tr style="height: 17px;">
| '''5''' || a || 3, 8, 13 || 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16,&nbsp;17 || '''5'''
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">1</span></strong></td>
|- style="background-color:#FFFFCC; height:17px;"
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">a</span></strong></td>
| '''5''' || b || 5, 9, 15 || 1, 2, 4, 5, 6, 7, 9, 11, 12, 14, 15, 16,&nbsp;17 || '''7'''
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">3, 8</span></strong></td>
|- style="background-color:#F5F5F5; height:17px;"
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">1, 2, 3, 4, 6, 7, 8</span></strong></td>
| '''6''' || a || 3, 8, 13 || 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16,&nbsp;17 || '''5'''
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">1</span></strong></td>
|- style="background-color:#F5F5F5; height:17px;"
</tr>
| '''6''' || b || 5, 15 || 1, 2, 4, 5, 6, 7, 11, 12, 14, 15, 16,&nbsp;17 || '''6'''
<tr style="height: 17px;">
|- style="background-color:#FFFFCC; height:17px;"
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">1</span></strong></td>
| '''7''' || a || 3, 8, 13 || 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16,&nbsp;17 || '''5'''
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">b</span></strong></td>
|- style="background-color:#FFFFCC; height:17px;"
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">5, 9</span></strong></td>
| '''7''' || b || 5, 10, 15 || 1, 2, 4, 5, 6, 7, 10, 11, 12, 14, 15, 16,&nbsp;17 || '''8'''
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">1, 2, 4, 5, 6, 7, 9</span></strong></td>
|- style="background-color:#F5F5F5; height:17px;"
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">3</span></strong></td>
| '''8''' || a || 3, 8, 13 || 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16,&nbsp;17 || '''5'''
</tr>
|- style="background-color:#F5F5F5; height:17px;"
<tr style="height: 17px;">
| '''8''' || b || 5, 15 || 1, 2, 4, 5, 6, 7, 11, 12, 14, 15, 16,&nbsp;17 || '''6'''
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">2</span></strong></td>
|}
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">a</span></strong></td>
 
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">3, 8</span></strong></td>
{{CollapsedCode|Determination table|{| border="1" cellspacing="0" style="font-family: Arial; text-align: center; border-collapse: collapse;"
<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 style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">1</span></strong></td>
! style="background-color:#FFCC99; height:44px; width:84px;" | '''In'''
</tr>
! style="background-color:#FFCC99; width:84px;" | '''&alpha;&isin;&Sigma;'''
<tr style="height: 17px;">
! style="background-color:#FFCC99; width:84px;" | '''move(In, &alpha;)'''
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">2</span></strong></td>
! style="background-color:#FFCC99; width:237px;" | '''&epsilon;-closure(move(In, &alpha;))'''
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">b</span></strong></td>
! style="background-color:#FFCC99; width:84px;" | '''In+1 = &epsilon;-closure(move(In, &alpha;))'''
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">5</span></strong></td>
|- style="background-color:#FFFFCC; height:17px;"
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">1, 2, 4, 5, 6, 7</span></strong></td>
| '''-''' || - || 0 || 0, 1, 2, 4, 7 || 0
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">2</span></strong></td>
|- style="background-color:#F5F5F5; height:17px;"
</tr>
| 0 || a || 3, 8 || 1, 2, 3, 4, 6, 7, 8 || 1
<tr style="height: 17px;">
|- style="background-color:#F5F5F5; height:17px;"
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">3</span></strong></td>
| 0 || b || 5 || 1, 2, 4, 5, 6, 7 || 2
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">a</span></strong></td>
|- style="background-color:#FFFFCC; height:17px;"
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">3, 8</span></strong></td>
| 1 || a || 3, 8 || 1, 2, 3, 4, 6, 7, 8 || 1
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">1, 2, 3, 4, 6, 7, 8</span></strong></td>
|- style="background-color:#FFFFCC; height:17px;"
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">1</span></strong></td>
| 1 || b || 5, 9 || 1, 2, 4, 5, 6, 7, 9 || 3
</tr>
|- style="background-color:#F5F5F5; height:17px;"
<tr style="height: 17px;">
| 2 || a || 3, 8 || 1, 2, 3, 4, 6, 7, 8 || 1
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">3</span></strong></td>
|- style="background-color:#F5F5F5; height:17px;"
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">b</span></strong></td>
| 2 || b || 5 || 1, 2, 4, 5, 6, 7 || 2
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">5, 10</span></strong></td>
|- style="background-color:#FFFFCC; height:17px;"
<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>
| 3 || a || 3, 8 || 1, 2, 3, 4, 6, 7, 8 || 1
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">4</span></strong></td>
|- style="background-color:#FFFFCC; height:17px;"
</tr>
| 3 || b || 5, 10 || 1, 2, 4, 5, 6, 7, 10, 11, 12, 14,&nbsp;17 || '''4'''
<tr style="height: 17px;">
|- style="background-color:#F5F5F5; height:17px;"
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">4</span></strong></td>
| '''4''' || a || 3, 8, 13 || 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16,&nbsp;17 || '''5'''
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">a</span></strong></td>
|- style="background-color:#F5F5F5; height:17px;"
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">3, 8, 13</span></strong></td>
| '''4''' || b || 5, 15 || 1, 2, 4, 5, 6, 7, 11, 12, 14, 15, 16,&nbsp;17 || '''6'''
<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>
|- style="background-color:#FFFFCC; height:17px;"
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">5</span></strong></td>
| '''5''' || a || 3, 8, 13 || 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16,&nbsp;17 || '''5'''
</tr>
|- style="background-color:#FFFFCC; height:17px;"
<tr style="height: 17px;">
| '''5''' || b || 5, 9, 15 || 1, 2, 4, 5, 6, 7, 9, 11, 12, 14, 15, 16,&nbsp;17 || '''7'''
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">4</span></strong></td>
|- style="background-color:#F5F5F5; height:17px;"
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">b</span></strong></td>
| '''6''' || a || 3, 8, 13 || 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16,&nbsp;17 || '''5'''
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">5, 15</span></strong></td>
|- style="background-color:#F5F5F5; height:17px;"
<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>
| '''6''' || b || 5, 15 || 1, 2, 4, 5, 6, 7, 11, 12, 14, 15, 16,&nbsp;17 || '''6'''
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">6</span></strong></td>
|- style="background-color:#FFFFCC; height:17px;"
</tr>
| '''7''' || a || 3, 8, 13 || 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16,&nbsp;17 || '''5'''
<tr style="height: 17px;">
|- style="background-color:#FFFFCC; height:17px;"
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">5</span></strong></td>
| '''7''' || b || 5, 10, 15 || 1, 2, 4, 5, 6, 7, 10, 11, 12, 14, 15, 16,&nbsp;17 || '''8'''
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">a</span></strong></td>
|- style="background-color:#F5F5F5; height:17px;"
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">3, 8, 13</span></strong></td>
| '''8''' || a || 3, 8, 13 || 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16,&nbsp;17 || '''5'''
<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>
|- style="background-color:#F5F5F5; height:17px;"
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">5</span></strong></td>
| '''8''' || b || 5, 15 || 1, 2, 4, 5, 6, 7, 11, 12, 14, 15, 16,&nbsp;17 || '''6'''
</tr>
|}
<tr style="height: 17px;">
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><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 style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">5, 9, 15</span></strong></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 style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">7</span></strong></td>
</tr>
<tr style="height: 17px;">
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><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 style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">3, 8, 13</span></strong></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 style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">5</span></strong></td>
</tr>
<tr style="height: 17px;">
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><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 style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">5, 15</span></strong></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 style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">6</span></strong></td>
</tr>
<tr style="height: 17px;">
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><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 style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">3, 8, 13</span></strong></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 style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">5</span></strong></td>
</tr>
<tr style="height: 17px;">
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><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 style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">5, 10, 15</span></strong></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 style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">8</span></strong></td>
</tr>
<tr style="height: 17px;">
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><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 style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">3, 8, 13</span></strong></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 style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">5</span></strong></td>
</tr>
<tr style="height: 17px;">
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><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 style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">5, 15</span></strong></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 style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">6</span></strong></td>
</tr>
</tbody>
</table>
}}
}}


Line 202: Line 150:


{{CollapsedCode|DFA|
{{CollapsedCode|DFA|
<graph>
<kroki lang="graphviz">
digraph dfa {
digraph dfa {
     { node [shape=circle style=invis] s }
     { node [shape=circle style=invis] s }
Line 228: Line 176:
   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>
</kroki>
}}
}}
The minimization tree is as follows:
The minimization tree is as follows:
Line 243: Line 190:


{{CollapsedCode|Minimal DFA|
{{CollapsedCode|Minimal DFA|
<graph>
<kroki lang="graphviz">
digraph dfamin {
digraph dfamin {
     { node [shape=circle style=invis] s }
     { node [shape=circle style=invis] s }
Line 259: Line 206:
   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>  
</kroki>  
}}
}}


Latest revision as of 18:36, 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)*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
Determination table
{

Graphically, the DFA is represented as follows:

DFA

The minimization tree is as follows:

Minimization tree

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

Minimal DFA
Retrieved from "https://robots.hlt.inesc-id.pt/w/pt/index.php?title=Theoretical_Aspects_of_Lexical_Analysis/Exercise_4&oldid=17696"