Theoretical Aspects of Lexical Analysis/Exercise 2: Difference between revisions

From Wiki**3

< Theoretical Aspects of Lexical Analysis
Root (talk | contribs)
PRIVATE, Bureaucrats, Administrators
15,362 edits
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*)*</nowiki>
 
Root (talk | contribs)
PRIVATE, Bureaucrats, Administrators
15,362 edits
No edit summary
 
(8 intermediate revisions by the same user not shown)
Line 1: Line 1:
__NOTOC__
== 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*)*</nowiki>
* '''<nowiki>(a*|b*)*</nowiki>'''
 
== Solution ==
 
The non-deterministic finite automaton (NFA), built by applying Thompson's algorithm to the regular expression '''<nowiki>(a*|b*)*</nowiki>''' is the following:
<kroki lang="graphviz">
digraph nfa {
    { node [shape=circle style=invis] start }
  rankdir=LR; ratio=0.5
  node [shape=doublecircle,fixedsize=true,width=0.2,fontsize=10]; 11
  node [shape=circle,fixedsize=true,width=0.2,fontsize=10];
  start -> 0
  0 -> 1; 0 -> 11
  1 -> 2; 1 -> 6
  2 -> 3; 2 -> 5
  3 -> 4 [label="a",fontsize=10]
  4 -> 3; 4 -> 5
  5 -> 10
  6 -> 7; 6 -> 9
  7 -> 8 [label="b",fontsize=10]
  8 -> 7; 8 -> 9
  9 -> 10
  10 -> 1; 10 -> 11
  fontsize=10
}
</kroki>
 
Applying the determination algorithm to the above NFA, the following determination table is obtained:
{| cellspacing="2"
! 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, 3, 5, 6, 7, 9, 10, '''11'''
! 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;" | 4
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 1, 2, 3, 4, 5, 6, 7, 9, 10, '''11'''
! 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;" | 8
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 1, 2, 3, 5, 6, 7, 8, 9, 10, '''11'''
! 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;" | 4
! style="font-weight: normal; align: left;  background: #ffffcc;" | 1, 2, 3, 4, 5, 6, 7, 9, 10, '''11'''
! 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;" | 8
! style="font-weight: normal; align: left;  background: #ffffcc;" | 1, 2, 3, 5, 6, 7, 8, 9, 10, '''11'''
! style="font-weight: normal; align: center; background: #ffffcc;" | '''2'''
|-
! 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;" | 4
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 1, 2, 3, 4, 5, 6, 7, 9, 10, '''11'''
! 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;" | 8
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 1, 2, 3, 5, 6, 7, 8, 9, 10, '''11'''
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''2'''
|}
 
{| width="100%"
! style="text-align: left; font-weight:normal; vertical-align: top; width: 50%;" |Graphically, the DFA is represented as follows:
<kroki lang="graphviz">
digraph dfa {
    { node [shape=circle style=invis] start }
  rankdir=LR; ratio=0.5
  node [shape=doublecircle,fixedsize=true,width=0.2,fontsize=10]; 0 1 2
  node [shape=circle,fixedsize=true,width=0.2,fontsize=10];
  start -> 0
  0 -> 1 [label="a"]
  0 -> 2 [label="b"]
  1 -> 1  [label="a"]
  1 -> 2  [label="b"]
  2 -> 1 [label="a"]
  2 -> 2 [label="b"]
  fontsize=10
}
</kroki>
 
Given the minimization tree to the right, the final minimal DFA is:
<kroki lang="graphviz">
digraph dfamin {
    { node [shape=circle style=invis] start }
  rankdir=LR; ratio=0.5
  node [shape=doublecircle,fixedsize=true,width=0.4,fontsize=10]; 012
  node [shape=circle,fixedsize=true,width=0.2,fontsize=10];
  start -> 012
  012 -> 012 [label="a"]
  012 -> 012 [label="b"]
  fontsize=10
}
</kroki>
 
! style="text-align: left; font-weight:normal; vertical-align: top; width: 50%;" | The minimization tree is as follows. As can be seen, the states are indistinguishable.
 
<kroki lang="graphviz">
digraph mintree {
  node [shape=none,fixedsize=true,width=0.2,fontsize=10]
  " {0, 1, 2}" -> "{}" [label="NF",fontsize=10]
  " {0, 1, 2}" -> "{0, 1, 2}" [label="  F",fontsize=10]
  "{0, 1, 2}" -> "{0, 1, 2} " [label="  a,b",fontsize=10]
  fontsize=10
}
</kroki>
|}
 
[[category:Compiladores]]
[[category:Ensino]]
 
[[en:Theoretical Aspects of Lexical Analysis]]

Latest revision as of 17:08, 6 August 2025


Problem

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

  • (a*|b*)*

Solution

The non-deterministic finite automaton (NFA), built by applying Thompson's algorithm to the regular expression (a*|b*)* is the following:

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

In α∈Σ move(In, α) ε-closure(move(In, α)) In+1 = ε-closure(move(In, α))
- - 0 0, 1, 2, 3, 5, 6, 7, 9, 10, 11 0
0 a 4 1, 2, 3, 4, 5, 6, 7, 9, 10, 11 1
0 b 8 1, 2, 3, 5, 6, 7, 8, 9, 10, 11 2
1 a 4 1, 2, 3, 4, 5, 6, 7, 9, 10, 11 1
1 b 8 1, 2, 3, 5, 6, 7, 8, 9, 10, 11 2
2 a 4 1, 2, 3, 4, 5, 6, 7, 9, 10, 11 1
2 b 8 1, 2, 3, 5, 6, 7, 8, 9, 10, 11 2
Graphically, the DFA is represented as follows:

Given the minimization tree to the right, the final minimal DFA is:

The minimization tree is as follows. As can be seen, the states are indistinguishable.
Retrieved from "https://robots.hlt.inesc-id.pt/w/pt/index.php?title=Theoretical_Aspects_of_Lexical_Analysis/Exercise_2&oldid=17368"