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

From Wiki**3

< Theoretical Aspects of Lexical Analysis
← Older editNewer edit →
Root (talk | contribs)
PRIVATE, Bureaucrats, Administrators
15,362 edits
No edit summary
Root (talk | contribs)
PRIVATE, Bureaucrats, Administrators
15,362 edits
Line 53: Line 53:


{{CollapsedCode|Determination table|
{{CollapsedCode|Determination table|
{| cellspacing="2"
<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;" | I<sub>n</sub>
<tbody>
! style="padding-left: 20px; padding-right: 20px; background: wheat;" | α∈Σ
<tr style="height: 44px;">
! style="padding-left: 20px; padding-right: 20px; background: wheat;" | move(I<sub>n</sub>, α)
<td style="height: 44px;" align="center" bgcolor="#FFCC99"><strong><span style="font-family: Arial;">In</span></strong></td>
! style="padding-left: 20px; padding-right: 20px; background: wheat;" | ε-closure(move(I<sub>n</sub>, α))
<td style="height: 44px;" align="center" bgcolor="#FFCC99"><strong><span style="font-family: Arial;">&alpha;&isin;&Sigma;</span></strong></td>
! style="padding-left: 20px; padding-right: 20px; background: wheat;" | I<sub>n+1</sub> = ε-closure(move(I<sub>n</sub>, α))
<td style="height: 44px;" 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>
! style="font-weight: normal; align: center; background: #ffffcc;" | -
<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="font-weight: normal; align: center; background: #ffffcc;" | -
</tr>
! style="font-weight: normal; align: center; background: #ffffcc;" | 0
<tr style="height: 17px;">
! style="font-weight: normal; align: left;  background: #ffffcc;" | 0, 1, 2, 4, 7
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">-</span></strong></td>
! style="font-weight: normal; align: center; background: #ffffcc;" | 0
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">-</span></strong></td>
|-
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">0</span></strong></td>
! style="font-weight: normal; align: center; background: #e6e6e6;" | 0
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">0, 1, 2, 4, 7</span></strong></td>
! style="font-weight: normal; align: center; background: #e6e6e6;" | a
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">0</span></strong></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="height: 17px;">
! style="font-weight: normal; align: center; background: #e6e6e6;" | 1
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">0</span></strong></td>
|-
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">a</span></strong></td>
! style="font-weight: normal; align: center; background: #e6e6e6;" | 0
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">3, 8</span></strong></td>
! style="font-weight: normal; align: center; background: #e6e6e6;" | b
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">1, 2, 3, 4, 6, 7, 8</span></strong></td>
! style="font-weight: normal; align: center; background: #e6e6e6;" | 5
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">1</span></strong></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 style="height: 17px;">
|-
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">0</span></strong></td>
! style="font-weight: normal; align: center; background: #ffffcc;" | 1
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">b</span></strong></td>
! style="font-weight: normal; align: center; background: #ffffcc;" | a
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">5</span></strong></td>
! style="font-weight: normal; align: center; background: #ffffcc;" | 3, 8
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">1, 2, 4, 5, 6, 7</span></strong></td>
! style="font-weight: normal; align: left;  background: #ffffcc;" | 1, 2, 3, 4, 6, 7, 8
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">2</span></strong></td>
! style="font-weight: normal; align: center; background: #ffffcc;" | 1
</tr>
|-
<tr style="height: 17px;">
! style="font-weight: normal; align: center; background: #ffffcc;" | 1
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">1</span></strong></td>
! style="font-weight: normal; align: center; background: #ffffcc;" | b
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">a</span></strong></td>
! style="font-weight: normal; align: center; background: #ffffcc;" | 5, 9
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">3, 8</span></strong></td>
! style="font-weight: normal; align: left;  background: #ffffcc;" | 1, 2, 4, 5, 6, 7, 9
<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="font-weight: normal; align: center; background: #ffffcc;" | 3
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">1</span></strong></td>
|-
</tr>
! style="font-weight: normal; align: center; background: #e6e6e6;" | 2
<tr style="height: 17px;">
! style="font-weight: normal; align: center; background: #e6e6e6;" | a
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">1</span></strong></td>
! style="font-weight: normal; align: center; background: #e6e6e6;" | 3, 8
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">b</span></strong></td>
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 1, 2, 3, 4, 6, 7, 8
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">5, 9</span></strong></td>
! style="font-weight: normal; align: center; background: #e6e6e6;" | 1
<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 style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">3</span></strong></td>
! style="font-weight: normal; align: center; background: #e6e6e6;" | 2
</tr>
! style="font-weight: normal; align: center; background: #e6e6e6;" | b
<tr style="height: 17px;">
! style="font-weight: normal; align: center; background: #e6e6e6;" | 5
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">2</span></strong></td>
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 1, 2, 4, 5, 6, 7
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">a</span></strong></td>
! style="font-weight: normal; align: center; background: #e6e6e6;" | 2
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">3, 8</span></strong></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>
! style="font-weight: normal; align: center; background: #ffffcc;" | 3
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">1</span></strong></td>
! style="font-weight: normal; align: center; background: #ffffcc;" | a
</tr>
! style="font-weight: normal; align: center; background: #ffffcc;" | 3, 8
<tr style="height: 17px;">
! style="font-weight: normal; align: left;  background: #ffffcc;" | 1, 2, 3, 4, 6, 7, 8
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">2</span></strong></td>
! style="font-weight: normal; align: center; background: #ffffcc;" | 1
<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</span></strong></td>
! style="font-weight: normal; align: center; background: #ffffcc;" | 3
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">1, 2, 4, 5, 6, 7</span></strong></td>
! style="font-weight: normal; align: center; background: #ffffcc;" | b
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">2</span></strong></td>
! style="font-weight: normal; align: center; background: #ffffcc;" | 5, 10
</tr>
! style="font-weight: normal; align: left;  background: #ffffcc;" | 1, 2, 4, 5, 6, 7, 10, 11, 12, 14, '''17'''
<tr style="height: 17px;">
! style="font-weight: normal; align: center; background: #ffffcc;" | '''4'''
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">3</span></strong></td>
|-
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">a</span></strong></td>
! style="font-weight: normal; align: center; background: #e6e6e6;" | 4
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">3, 8</span></strong></td>
! style="font-weight: normal; align: center; background: #e6e6e6;" | a
<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="font-weight: normal; align: center; background: #e6e6e6;" | 3, 8, 13
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">1</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 style="height: 17px;">
|-
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">3</span></strong></td>
! style="font-weight: normal; align: center; background: #e6e6e6;" | 4
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">b</span></strong></td>
! style="font-weight: normal; align: center; background: #e6e6e6;" | b
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">5, 10</span></strong></td>
! style="font-weight: normal; align: center; background: #e6e6e6;" | 5, 15
<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>
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 1, 2, 4, 5, 6, 7, 11, 12, 14, 15, 16, '''17'''
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">4</span></strong></td>
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''6'''
</tr>
|-
<tr style="height: 17px;">
! style="font-weight: normal; align: center; background: #ffffcc;" | 5
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">4</span></strong></td>
! style="font-weight: normal; align: center; background: #ffffcc;" | a
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">a</span></strong></td>
! style="font-weight: normal; align: center; background: #ffffcc;" | 3, 8, 13
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">3, 8, 13</span></strong></td>
! style="font-weight: normal; align: left;  background: #ffffcc;" | 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16, '''17'''
<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="font-weight: normal; align: center; background: #ffffcc;" | '''5'''
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">5</span></strong></td>
|-
</tr>
! style="font-weight: normal; align: center; background: #ffffcc;" | 5
<tr style="height: 17px;">
! style="font-weight: normal; align: center; background: #ffffcc;" | b
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">4</span></strong></td>
! style="font-weight: normal; align: center; background: #ffffcc;" | 5, 9, 15
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">b</span></strong></td>
! style="font-weight: normal; align: left;  background: #ffffcc;" | 1, 2, 4, 5, 6, 7, 9, 11, 12, 14, 15, 16, '''17'''
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">5, 15</span></strong></td>
! style="font-weight: normal; align: center; background: #ffffcc;" | '''7'''
<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>
! style="font-weight: normal; align: center; background: #e6e6e6;" | 6
</tr>
! style="font-weight: normal; align: center; background: #e6e6e6;" | a
<tr style="height: 17px;">
! style="font-weight: normal; align: center; background: #e6e6e6;" | 3, 8, 13
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">5</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 style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">a</span></strong></td>
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''5'''
<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>
! style="font-weight: normal; align: center; background: #e6e6e6;" | 6
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">5</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="height: 17px;">
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 1, 2, 4, 5, 6, 7, 11, 12, 14, 15, 16, '''17'''
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">5</span></strong></td>
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''6'''
<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>
! style="font-weight: normal; align: center; background: #ffffcc;" | 7
<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>
! style="font-weight: normal; align: center; background: #ffffcc;" | a
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">7</span></strong></td>
! 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'''
<tr style="height: 17px;">
! style="font-weight: normal; align: center; background: #ffffcc;" | '''5'''
<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>
! style="font-weight: normal; align: center; background: #ffffcc;" | 7
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">3, 8, 13</span></strong></td>
! style="font-weight: normal; align: center; background: #ffffcc;" | b
<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="font-weight: normal; align: center; background: #ffffcc;" | 5, 10, 15
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">5</span></strong></td>
! style="font-weight: normal; align: left;  background: #ffffcc;" | 1, 2, 4, 5, 6, 7, 10, 11, 12, 14, 15, 16, '''17'''
</tr>
! style="font-weight: normal; align: center; background: #ffffcc;" | '''8'''
<tr style="height: 17px;">
|-
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">6</span></strong></td>
! style="font-weight: normal; align: center; background: #e6e6e6;" | 8
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">b</span></strong></td>
! style="font-weight: normal; align: center; background: #e6e6e6;" | a
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">5, 15</span></strong></td>
! style="font-weight: normal; align: center; background: #e6e6e6;" | 3, 8, 13
<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>
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16, '''17'''
<td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">6</span></strong></td>
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''5'''
</tr>
|-
<tr style="height: 17px;">
! style="font-weight: normal; align: center; background: #e6e6e6;" | 8
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">7</span></strong></td>
! style="font-weight: normal; align: center; background: #e6e6e6;" | b
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">a</span></strong></td>
! style="font-weight: normal; align: center; background: #e6e6e6;" | 5, 15
<td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">3, 8, 13</span></strong></td>
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 1, 2, 4, 5, 6, 7, 11, 12, 14, 15, 16, '''17'''
<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="font-weight: normal; align: center; background: #e6e6e6;" | '''6'''
<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>
}}
}}


Revision as of 07:58, 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
b)*abb(a

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

Determination table
{{{2}}}

Graphically, the DFA is represented as follows:

DFA
b)*abb(a

The minimization tree is as follows:

Minimization tree

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

Minimal DFA
b)*abb(a
Retrieved from "https://robots.hlt.inesc-id.pt/w/pt/index.php?title=Theoretical_Aspects_of_Lexical_Analysis/Exercise_4&oldid=7687"