Difference between revisions of "Theoretical Aspects of Lexical Analysis/Exercise 4"

From Wiki**3

< Theoretical Aspects of Lexical Analysis
(→‎DFA)
Line 99: Line 99:
 
! style="font-weight: normal; align: center; background: #e6e6e6;" | 2
 
! style="font-weight: normal; align: center; background: #e6e6e6;" | 2
 
|-
 
|-
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | 3
+
! style="font-weight: normal; align: center; background: #ffffcc;" | 3
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | a
+
! style="font-weight: normal; align: center; background: #ffffcc;" | a
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | 3, 8
+
! style="font-weight: normal; align: center; background: #ffffcc;" | 3, 8
−
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 1, 2, 3, 4, 6, 7, 8
+
! style="font-weight: normal; align: left;  background: #ffffcc;" | 1, 2, 3, 4, 6, 7, 8
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | 1
+
! style="font-weight: normal; align: center; background: #ffffcc;" | 1
 
|-
 
|-
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | 3
+
! style="font-weight: normal; align: center; background: #ffffcc;" | 3
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | b  
+
! style="font-weight: normal; align: center; background: #ffffcc;" | b  
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | 5, 10
+
! style="font-weight: normal; align: center; background: #ffffcc;" | 5, 10
−
! style="font-weight: normal; align: left;  background: #e6e6e6;" | 1, 2, 4, 5, 6, 7, 10, 11, 12, 14, '''17'''
+
! 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: #e6e6e6;" | '''4'''
+
! 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;" | 4
Line 123: Line 123:
 
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''6'''
 
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''6'''
 
|-
 
|-
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | 5
+
! style="font-weight: normal; align: center; background: #ffffcc;" | 5
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | a
+
! style="font-weight: normal; align: center; background: #ffffcc;" | a
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | 3, 8, 13
+
! style="font-weight: normal; align: center; background: #ffffcc;" | 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: left;  background: #ffffcc;" | 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: #ffffcc;" | '''5'''
 
|-
 
|-
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | 5
+
! style="font-weight: normal; align: center; background: #ffffcc;" | 5
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | b  
+
! style="font-weight: normal; align: center; background: #ffffcc;" | b  
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | 5, 15
+
! style="font-weight: normal; align: center; background: #ffffcc;" | 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: left;  background: #ffffcc;" | 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;" | '''6'''
 
|-
 
|-
 
! style="font-weight: normal; align: center; background: #e6e6e6;" | 6
 
! style="font-weight: normal; align: center; background: #e6e6e6;" | 6

Revision as of 06:07, 22 March 2009

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)*

NFA

The following is the result of applying Thompson's algorithm.


DFA

Determination table for the above NFA:

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, 15 1, 2, 4, 5, 6, 7, 11, 12, 14, 15, 16, 17 6
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


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.


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.

Retrieved from "https://web.tecnico.ulisboa.pt/~david.matos/w/pt/index.php?title=Theoretical_Aspects_of_Lexical_Analysis/Exercise_4&oldid=3070"