(New page: Use Thompson's algorithm to build the NFA for the following regular expression. Build the corresponding DFA and minimize it. * <nowiki>(a|b)*abb(a|b)*</nowiki> == Solution == [[category...) |
|||
(24 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> | + | |
+ | ==Problem == | ||
+ | Use Thompson's algorithm to build the NFA for the following regular expression. Build the corresponding DFA and minimize it. | ||
+ | |||
+ | * '''<nowiki>(a|b)*abb(a|b)*</nowiki>''' | ||
== Solution == | == Solution == | ||
− | [[category: | + | 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: |
− | [[category: | + | {{CollapsedCode|NFA| |
+ | <dot-hack> | ||
+ | digraph nfa { | ||
+ | { node [shape=circle style=invis] s } | ||
+ | rankdir=LR; ratio=0.5 | ||
+ | node [shape=doublecircle,fixedsize=true,width=0.2,fontsize=10]; 17 | ||
+ | node [shape=circle,fixedsize=true,width=0.2,fontsize=10]; | ||
+ | |||
+ | s -> 0 | ||
+ | 0 -> 1 | ||
+ | 1 -> 2 | ||
+ | 1 -> 4 | ||
+ | 2 -> 3 [label="a",fontsize=10] | ||
+ | 4 -> 5 [label="b",fontsize=10] | ||
+ | 3 -> 6 | ||
+ | 5 -> 6 | ||
+ | 6 -> 1 | ||
+ | 6 -> 7 | ||
+ | 0 -> 7 | ||
+ | |||
+ | 7 -> 8 [label="a",fontsize=10] | ||
+ | 8 -> 9 [label="b",fontsize=10] | ||
+ | 9 -> 10 [label="b",fontsize=10] | ||
+ | |||
+ | 10 -> 11 | ||
+ | 11 -> 12 | ||
+ | 11 -> 14 | ||
+ | 12 -> 13 [label="a",fontsize=10] | ||
+ | 14 -> 15 [label="b",fontsize=10] | ||
+ | 13 -> 16 | ||
+ | 15 -> 16 | ||
+ | 16 -> 11 | ||
+ | 16 -> 17 | ||
+ | 10 -> 17 | ||
+ | |||
+ | fontsize=10 | ||
+ | } | ||
+ | </dot-hack> | ||
+ | }} | ||
+ | |||
+ | Applying the determination algorithm to the above NFA, the following determination table is obtained: | ||
+ | |||
+ | {{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;">α∈Σ</span></strong></td> | ||
+ | <td align="center" bgcolor="#FFCC99"><strong><span style="font-family: Arial;">move(In, α)</span></strong></td> | ||
+ | <td align="center" bgcolor="#FFCC99"><strong><span style="font-family: Arial;">ε-closure(move(In, α))</span></strong></td> | ||
+ | <td align="center" bgcolor="#FFCC99"><strong><span style="font-family: Arial;">In+1 = ε-closure(move(In, α))</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, 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, 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, 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, 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, 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, 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, 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, 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, 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, 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, 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: | ||
+ | |||
+ | {{CollapsedCode|DFA| | ||
+ | <dot-hack> | ||
+ | digraph dfa { | ||
+ | { node [shape=circle style=invis] s } | ||
+ | rankdir=LR; ratio=0.5 | ||
+ | node [shape=doublecircle,fixedsize=true,width=0.2,fontsize=10]; 4 5 6 7 8 | ||
+ | node [shape=circle,fixedsize=true,width=0.2,fontsize=10]; | ||
+ | s -> 0 | ||
+ | 0 -> 1 [label="a",fontsize=10] | ||
+ | 0 -> 2 [label="b",fontsize=10] | ||
+ | 1 -> 1 [label="a",fontsize=10] | ||
+ | 1 -> 3 [label="b",fontsize=10] | ||
+ | 2 -> 1 [label="a",fontsize=10] | ||
+ | 2 -> 2 [label="b",fontsize=10] | ||
+ | 3 -> 1 [label="a",fontsize=10] | ||
+ | 3 -> 4 [label="b",fontsize=10] | ||
+ | 4 -> 5 [label="a",fontsize=10] | ||
+ | 4 -> 6 [label="b",fontsize=10] | ||
+ | 5 -> 5 [label="a",fontsize=10] | ||
+ | 5 -> 7 [label="b",fontsize=10] | ||
+ | 6 -> 5 [label="a",fontsize=10] | ||
+ | 6 -> 6 [label="b",fontsize=10] | ||
+ | 7 -> 5 [label="a",fontsize=10] | ||
+ | 7 -> 8 [label="b",fontsize=10] | ||
+ | 8 -> 5 [label="a",fontsize=10] | ||
+ | 8 -> 6 [label="b",fontsize=10] | ||
+ | fontsize=10 | ||
+ | } | ||
+ | </dot-hack> | ||
+ | }} | ||
+ | The minimization tree is as follows: | ||
+ | |||
+ | {{CollapsedCode|Minimization tree| | ||
+ | [[image:aula3p4mintree.jpg|350px]] | ||
+ | }} | ||
+ | |||
+ | <!--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: | ||
+ | |||
+ | {{CollapsedCode|Minimal DFA| | ||
+ | <dot-hack> | ||
+ | digraph dfamin { | ||
+ | { node [shape=circle style=invis] s } | ||
+ | rankdir=LR; ratio=0.5 | ||
+ | node [shape=doublecircle,fixedsize=true,width=0.4,fontsize=10]; 45678 | ||
+ | node [shape=circle,fixedsize=true,width=0.3,fontsize=10]; | ||
+ | s -> 02 | ||
+ | 02 -> 1 [label="a",fontsize=10] | ||
+ | 02 -> 02 [label="b",fontsize=10] | ||
+ | 1 -> 1 [label="a",fontsize=10] | ||
+ | 1 -> 3 [label="b",fontsize=10] | ||
+ | 3 -> 1 [label="a",fontsize=10] | ||
+ | 3 -> 45678 [label="b",fontsize=10] | ||
+ | 45678 -> 45678 [label="a",fontsize=10] | ||
+ | 45678 -> 45678 [label="b",fontsize=10] | ||
+ | fontsize=10 | ||
+ | } | ||
+ | </dot-hack> | ||
+ | }} | ||
+ | |||
+ | [[category:Compiladores]] | ||
+ | [[category:Ensino]] | ||
+ | |||
[[en:Theoretical Aspects of Lexical Analysis]] | [[en:Theoretical Aspects of Lexical Analysis]] |
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 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
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 |
---|