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
 
(13 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>


== NFA ==
==Problem ==  
Use Thompson's algorithm to build the NFA for the following regular expression. Build the corresponding DFA and minimize it.


The following is the result of applying Thompson's algorithm.
* '''<nowiki>(a|b)*abb(a|b)*</nowiki>'''


<graph>
== Solution ==
 
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|
<kroki lang="graphviz">
digraph nfa {
digraph nfa {
     { node [shape=circle style=invis] s }
     { node [shape=circle style=invis] s }
Line 39: Line 43:
   16 -> 17
   16 -> 17
   10 -> 17
   10 -> 17


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


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


Determination table for the above NFA:
{| class="mw-collapsible mw-collapsed" border="1" cellspacing="0" style="font-family: Arial; text-align: center; border-collapse: collapse;"
|+ '''Determination table'''
|-
! style="background-color:#FFCC99; height:44px; width:84px;" | '''In'''
! style="background-color:#FFCC99; width:84px;" | '''&alpha;&isin;&Sigma;'''
! style="background-color:#FFCC99; width:84px;" | '''move(In, &alpha;)'''
! style="background-color:#FFCC99; width:237px;" | '''&epsilon;-closure(move(In, &alpha;))'''
! style="background-color:#FFCC99; width:84px;" | '''In+1 = &epsilon;-closure(move(In, &alpha;))'''
|- style="background-color:#FFFFCC; height:17px;"
| '''-''' || - || 0 || 0, 1, 2, 4, 7 || 0
|- style="background-color:#F5F5F5; height:17px;"
| 0 || a || 3, 8 || 1, 2, 3, 4, 6, 7, 8 || 1
|- style="background-color:#F5F5F5; height:17px;"
| 0 || b || 5 || 1, 2, 4, 5, 6, 7 || 2
|- style="background-color:#FFFFCC; height:17px;"
| 1 || a || 3, 8 || 1, 2, 3, 4, 6, 7, 8 || 1
|- style="background-color:#FFFFCC; height:17px;"
| 1 || b || 5, 9 || 1, 2, 4, 5, 6, 7, 9 || 3
|- style="background-color:#F5F5F5; height:17px;"
| 2 || a || 3, 8 || 1, 2, 3, 4, 6, 7, 8 || 1
|- style="background-color:#F5F5F5; height:17px;"
| 2 || b || 5 || 1, 2, 4, 5, 6, 7 || 2
|- style="background-color:#FFFFCC; height:17px;"
| 3 || a || 3, 8 || 1, 2, 3, 4, 6, 7, 8 || 1
|- style="background-color:#FFFFCC; height:17px;"
| 3 || b || 5, 10 || 1, 2, 4, 5, 6, 7, 10, 11, 12, 14,&nbsp;17 || '''4'''
|- style="background-color:#F5F5F5; height:17px;"
| '''4''' || a || 3, 8, 13 || 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16,&nbsp;17 || '''5'''
|- style="background-color:#F5F5F5; height:17px;"
| '''4''' || b || 5, 15 || 1, 2, 4, 5, 6, 7, 11, 12, 14, 15, 16,&nbsp;17 || '''6'''
|- style="background-color:#FFFFCC; height:17px;"
| '''5''' || a || 3, 8, 13 || 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16,&nbsp;17 || '''5'''
|- style="background-color:#FFFFCC; height:17px;"
| '''5''' || b || 5, 9, 15 || 1, 2, 4, 5, 6, 7, 9, 11, 12, 14, 15, 16,&nbsp;17 || '''7'''
|- style="background-color:#F5F5F5; height:17px;"
| '''6''' || a || 3, 8, 13 || 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16,&nbsp;17 || '''5'''
|- style="background-color:#F5F5F5; height:17px;"
| '''6''' || b || 5, 15 || 1, 2, 4, 5, 6, 7, 11, 12, 14, 15, 16,&nbsp;17 || '''6'''
|- style="background-color:#FFFFCC; height:17px;"
| '''7''' || a || 3, 8, 13 || 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16,&nbsp;17 || '''5'''
|- style="background-color:#FFFFCC; height:17px;"
| '''7''' || b || 5, 10, 15 || 1, 2, 4, 5, 6, 7, 10, 11, 12, 14, 15, 16,&nbsp;17 || '''8'''
|- style="background-color:#F5F5F5; height:17px;"
| '''8''' || a || 3, 8, 13 || 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16,&nbsp;17 || '''5'''
|- style="background-color:#F5F5F5; height:17px;"
| '''8''' || b || 5, 15 || 1, 2, 4, 5, 6, 7, 11, 12, 14, 15, 16,&nbsp;17 || '''6'''
|}


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


Graphically, the DFA is represented as follows:
Graphically, the DFA is represented as follows:


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


== Minimal DFA ==
{{CollapsedCode|Minimization tree|
[[image:aula3p4mintree.jpg|350px]]
}}


The minimization tree is as follows.
<!--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:


<graph>
{{CollapsedCode|Minimal DFA|
digraph mintree {  
<kroki lang="graphviz">
  node [shape=none,fixedsize=true,width=0.7,fontsize=10]
  "{0, 1, 2, 3, 4, 5, 6, 7, 8} " -> "{0, 1, 2, 3}" [label="NF",fontsize=10]
  "{0, 1, 2, 3, 4, 5, 6, 7, 8} " -> "{4, 5, 6, 7, 8}" [label="  F",fontsize=10]
  "{0, 1, 2, 3}" ->  "{0, 1, 2}"
  "{0, 1, 2, 3}" -> "{3} " [label=" b",fontsize=10]
  "{0, 1, 2}" -> "{0, 2} "
  "{0, 1, 2}" -> "{1} " [label="  b",fontsize=10]
  fontsize=10
  //label="Minimization tree"
}
</graph>
 
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 either "a" or "b" transitions.
 
Given the minimization tree above, the final minimal DFA is:
<graph>
digraph dfamin {
digraph dfamin {
     { node [shape=circle style=invis] s }
     { node [shape=circle style=invis] s }
   rankdir=LR; ratio=0.5
   rankdir=LR; ratio=0.5
   node [shape=doublecircle,fixedsize=true,width=0.4,fontsize=10]; 456
   node [shape=doublecircle,fixedsize=true,width=0.4,fontsize=10]; 45678
   node [shape=circle,fixedsize=true,width=0.3,fontsize=10];
   node [shape=circle,fixedsize=true,width=0.3,fontsize=10];
   s -> 02
   s -> 02
Line 238: Line 202:
   1 -> 3  [label="b",fontsize=10]
   1 -> 3  [label="b",fontsize=10]
   3 -> 1 [label="a",fontsize=10]
   3 -> 1 [label="a",fontsize=10]
   3 -> 456 [label="b",fontsize=10]
   3 -> 45678 [label="b",fontsize=10]
   45678 -> 45678 [label="a",fontsize=10]
   45678 -> 45678 [label="a",fontsize=10]
   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>  
}}
 
[[category:Compiladores]]
[[category:Ensino]]


[[category:Teaching]]
[[category:Compilers]]
[[en:Theoretical Aspects of Lexical Analysis]]
[[en:Theoretical Aspects of Lexical Analysis]]

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"