(→Solution) |
|||
Line 53: | Line 53: | ||
{{CollapsedCode|Determination table| | {{CollapsedCode|Determination table| | ||
− | + | <table border="1" cellspacing="0"><colgroup span="3" width="84"></colgroup> <colgroup width="237"></colgroup> <colgroup width="84"></colgroup> | |
− | + | <tbody> | |
− | + | <tr style="height: 44px;"> | |
− | + | <td style="height: 44px;" align="center" bgcolor="#FFCC99"><strong><span style="font-family: Arial;">In</span></strong></td> | |
− | + | <td style="height: 44px;" align="center" bgcolor="#FFCC99"><strong><span style="font-family: Arial;">α∈Σ</span></strong></td> | |
− | + | <td style="height: 44px;" align="center" bgcolor="#FFCC99"><strong><span style="font-family: Arial;">move(In, α)</span></strong></td> | |
− | + | <td style="height: 44px;" align="center" bgcolor="#FFCC99"><strong><span style="font-family: Arial;">ε-closure(move(In, α))</span></strong></td> | |
− | + | <td style="height: 44px;" align="center" bgcolor="#FFCC99"><strong><span style="font-family: Arial;">In+1 = ε-closure(move(In, α))</span></strong></td> | |
− | + | </tr> | |
− | + | <tr style="height: 17px;"> | |
− | + | <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;">-</span></strong></td> | |
− | + | <td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">0</span></strong></td> | |
− | + | <td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">0, 1, 2, 4, 7</span></strong></td> | |
− | + | <td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">0</span></strong></td> | |
− | + | </tr> | |
− | + | <tr style="height: 17px;"> | |
− | + | <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> | |
− | + | <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> | |
− | + | <td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">1</span></strong></td> | |
− | + | </tr> | |
− | + | <tr style="height: 17px;"> | |
− | + | <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;">b</span></strong></td> | |
− | + | <td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">5</span></strong></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 style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">2</span></strong></td> | |
− | + | </tr> | |
− | + | <tr style="height: 17px;"> | |
− | + | <td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">1</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</span></strong></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 style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">1</span></strong></td> | |
− | + | </tr> | |
− | + | <tr style="height: 17px;"> | |
− | + | <td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">1</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</span></strong></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 style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">3</span></strong></td> | |
− | + | </tr> | |
− | + | <tr style="height: 17px;"> | |
− | + | <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> | |
− | + | <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> | |
− | + | </tr> | |
− | + | <tr style="height: 17px;"> | |
− | + | <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;">b</span></strong></td> | |
− | + | <td style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">5</span></strong></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 style="height: 17px;" align="center" bgcolor="#F5F5F5"><strong><span style="font-family: Arial;">2</span></strong></td> | |
− | + | </tr> | |
− | + | <tr style="height: 17px;"> | |
− | + | <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> | |
− | + | <td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">3, 8</span></strong></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 style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">1</span></strong></td> | |
− | + | </tr> | |
− | + | <tr style="height: 17px;"> | |
− | + | <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;">b</span></strong></td> | |
− | + | <td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">5, 10</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, 17</span></strong></td> | |
− | + | <td style="height: 17px;" align="center" bgcolor="#FFFFCC"><strong><span style="font-family: Arial;">4</span></strong></td> | |
− | + | </tr> | |
− | + | <tr style="height: 17px;"> | |
− | + | <td style="height: 17px;" align="center" bgcolor="#F5F5F5"><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 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, 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;">4</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, 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;">5</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, 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;">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, 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, 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, 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, 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, 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, 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, 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> | ||
}} | }} | ||
Contents |
Use Thompson's algorithm to build the NFA for the following regular expression. Build the corresponding DFA and minimize it.
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 |
---|
{{{2}}} |
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 |
---|
|