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
 
(5 intermediate revisions by the same user not shown)
Line 1: Line 1:
{{TOCright}}
{{TOCright}}


==Problem??
==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.


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


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


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


{{CollapsedCode|Minimization tree|
{{CollapsedCode|Minimization tree|
[[image:aula3p4mintree.jpg|200]]
[[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).  
<!--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:


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


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"