Report

DFA vs NFA Deterministic Finite Automata Non-Deterministic Finite Automata Characterized as 5-tuple < S, A, T, s0, F > • S is the set of states • A is the alphabet • T is the transition function: S xA S • s0 is the start state • F is the set of accepting states. Characterized as 5-tuple < S, A, T, s0, F > • S is the set of states • A is the alphabet • T is the transition function: S x (A{}) PS • s0 is the start state • F is the set of accepting states. Waseem Besada 1 From NFA To DFA 1 Transition function for NFA T a b 0 {1} ø {3} b a 2 0 a 1 ø {2} ø 2 ø ø ø 3 {3} ø {4} 4 {2} ø ø a Waseem Besada 4 3 2 Calculating The Transition function for DFA Transition function for DFA Transition function for NFA T a b T a b {0,3,4} ? ? 0 {1} ø {3} 1 ø {2} ø 2 ø ø ø 3 {3} ø {4} 4 {2} ø ø TD({0,3,4},a) = ({0},a) ({3},a) ({4},a) = {1,3} {3,4} {2} = {1,2,3,4} TD({0,3,4},b) = ({0},b) ({3},b) ({4},b) =øøø =ø Waseem Besada 3 Calculating The Transition function for DFA (forts) Transition function for DFA Transition function for NFA T a b T a b {0,3,4} {1,2,3,4} 0 {1} ø {3} ø ø? ø ?ø 1 ø {2} ø {1,2,3,4} {2,3,4} ? {2} ? 2 ø ø ø 3 {3} ø {4} 4 {2} ø ø TD({1,2,3,4},a) = ({1},a) ({2},a) ({3},a) ({2},a) = ø ø {3,4} {2} = {2,3,4} Similarly, TD({1,2,3,4},b) = {2} Waseem Besada 4 Calculating The Transition function for DFA (forts) Transition function for DFA Transition function for NFA a b T a b {0,3,4} {1,2,3,4} ø 0 {1} ø {3} ø ø ø 1 ø {2} ø {1,2,3,4} {2,3,4} {2} 2 ø ø ø {2,3,4} {2,3,4} {2} 3 {3} ø {4} {2} ø ø 4 {2} ø ø T Waseem Besada 5 Finally b Transition function for DFA 4 b 0 a T a,b 2 1 a b 3 a 0 1 2 3 4 Waseem Besada a b {0,3,4} {1,2,3,4} ø ø? ø ?ø {1,2,3,4} {2,3,4} {2} {2,3,4} {2,3,4} {2} {2} ø ø 6 Exercise 2, solution 2. Construct directly (that is don’t use the transformation procedure given in the lecture) a DFA for each of the following REs. a) a | b b) a | b* c) ab* | bc* b a a,b b a,b a,b a a a,b c a) b a b a,b a,c b a,b,c a,b c c) b) Waseem Besada 7 Exercise 4, solution 4. Construct directly (that is don’t use the transformation procedure given in the lecture) a NFA for each of the following REs. a) a*bc*| bc b) a* | ab a c a b a c a b b) a) Waseem Besada 8 Exercise 5 5. Construct a DFA table for the following NFA transition table. The start state is 0 and there is one accepting state, 2. a 0 Ø 1 {2} 2 Ø b {1,2} Ø {2} {1} Ø {1} b 1 0 a b 2 b Waseem Besada 9 Solution to exercise 5 NFA transition table DFA transition table T a b a {0,1} {1,2} ? {1,2} ? 0 {1,2} 0 Ø 1 {2} 2 Ø {1,2} {1,2} b {1,2} Ø {2} {1} Ø {1} 1 0 a,b Waseem Besada 1 a,b 10 Exercise 6 6. Consider the following NFA over the alphabet {a,b}: a) Find a regular expression for the language accepted by the NFA. b) Write down the transition table for the NFA. c) Transform the NFA into a DFA d) Draw a picture of the resulting DFA. a 0 0 a Waseem Besada b 0 11 Solution to exercise 6 (cont’d) Transition table for NFA T a b 0 0 1 2 {1} Ø {2} Ø {2} Ø a 1 a {1,2} Ø Ø Waseem Besada b 2 12 Solution to exercise 6 (cont’d) Transition table for NFA Transition table for DFA T a b {0,1,2} {1,2} {1,2} {2} {2} {2} Ø Ø T a {2} {2} Ø Ø b 0 {1} Ø {1,2} 1 Ø {2} Ø 2 {2} Ø Ø Waseem Besada 13 Solution to exercise 6(cont’d) {0,1,2} a {1,2} b a,b {2} Transition table for DFA T a b {0,1,2} {1,2} {1,2} {2} {2} {2} Ø Ø {2} {2} Ø Ø a Waseem Besada 14 Exercise 7 7. Transform each of the following REs into a NFA, then into a DFA a) a*b* b) a* | b* Solution to a) 0 2 1 4 a b c) (a|b)* 3 6 0 a 1 b 6 5 Waseem Besada 15 Solution, exercise 6-a T {0,1,2,3} {1,2,3} {2,3} Ø a b {1,2,3} {1,2,3} Ø Ø a a 0 {2,3} {2,3} {2,3} Ø a a 0 1 b a,b a 2 3 2 3 a,b b b Can be reduced to: 0 1 b 2 a 3 b b Waseem Besada 16 What to do next? It is your turn to solve the rest of the exercises Waseem Besada 17