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
No edit summary
Root (talk | contribs)
PRIVATE, Bureaucrats, Administrators
15,362 edits
No edit summary
 
(7 intermediate revisions by the same user not shown)
Line 1: Line 1:
__NOTOC__
{{TOCright}}
<div class="section-container auto" data-section>
 
  <div class="section">
==Problem ==  
    <p class="title" data-section-title>Problem</p>
    <div class="content" data-section-content>
<!-- ====================== START OF PROBLEM ====================== -->
Use Thompson's algorithm to build the NFA for the following regular expression. Build the corresponding DFA and minimize it.
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>'''
* '''<nowiki>(a|b)*abb(a|b)*</nowiki>'''
<!-- ====================== END OF PROBLEM ====================== -->
 
    </div>
== Solution ==
  </div>
 
  <div class="section">
    <p class="title" data-section-title>Solution</p>
    <div class="content" data-section-content>
<!-- ====================== START OF 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:
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:
<graph>
{{CollapsedCode|NFA|
<kroki lang="graphviz">
digraph nfa {
digraph nfa {
     { node [shape=circle style=invis] s }
     { node [shape=circle style=invis] s }
Line 51: 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:


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


<graph>
{{CollapsedCode|Minimization tree|
digraph mintree {  
[[image:aula3p4mintree.jpg|350px]]
  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 both "a" or "b" transitions (remember that, at this stage, we assume that individual states -- i.e., the final states -- are all indistinguishable).


<!--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:
Given the minimization tree above, the final minimal DFA is as follows:


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


[[category:Compiladores]]
[[category:Compiladores]]

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"