4-Regular expression to Deterministic Finite Automata (Direct method)-05-05-2023.pptx

.

1. Subset construction algorithm Input : An NFA . Output : A DFA D accepting the same language. Method : Algorithm construct a transition table for D. We use the following operation:   OPERATION DESCRIPTION Set of NFA states reachable from NFA state on – transition alone. Set of NFA states reachable from some NFA state in on – transition alone. Set of NFA states to which there is a transition on input symbol from some NFA state in .

2. Subset construction algorithm initially be the only state in and it is unmarked; while there is unmarked states T in do begin mark ; for each input symbol do begin if is not in then add as unmarked state to end end  

3. Conversion from NFA to DFA 1 (a|b) * abb 2 5 3 4 6 7 8 9 10 𝜖 a b 𝜖 a b b 𝜖 𝜖 𝜖 𝜖 𝜖 𝜖

4. Conversion from NFA to DFA 1 2 5 3 4 6 7 8 9 𝜖 a b 𝜖 a b b 𝜖 𝜖 𝜖 𝜖 𝜖 𝜖 10 {0, 1, 7, 2, 4} ---- A 𝜖- Closure(0 )= = {0,1,2,4,7}

5. Conversion from NFA to DFA 1 2 5 3 4 6 7 8 9 𝜖 a b 𝜖 a b b 𝜖 𝜖 𝜖 𝜖 𝜖 𝜖 A= {0, 1, 2, 4, 7} Move(A,a) = {3,8} 𝜖- Closure( Move(A,a)) = {3, 6, 7, 1, 2, 4, 8} ---- B = {1,2,3,4,6,7,8} 10 States a b A = {0,1,2,4,7} B B = {1,2,3,4,6,7,8}

6. Conversion from NFA to DFA 1 2 5 3 4 6 7 8 𝜖 a b 𝜖 a b b 𝜖 𝜖 𝜖 𝜖 𝜖 𝜖 A= {0, 1, 2, 4, 7} Move(A,b) = {5} 𝜖- Closure( Move(A,b)) = {5, 6, 7, 1, 2, 4} ---- C = {1,2,4,5,6,7} {5} 10 9 States a b A = {0,1,2,4,7} B C B = {1,2,3,4,6,7,8} C = {1,2,4,5,6,7}

7. Conversion from NFA to DFA 1 2 5 3 4 6 7 8 𝜖 a b 𝜖 a b 𝜖 𝜖 𝜖 𝜖 𝜖 𝜖 B = {1, 2, 3, 4, 6, 7, 8} Move(B,a) = {3,8} 𝜖- Closure( Move(B,a)) = {3, 6, 7, 1, 2, 4, 8} ---- B = {1,2,3,4,6,7,8} b 10 9 States a b A = {0,1,2,4,7} B C B = {1,2,3,4,6,7,8} B C = {1,2,4,5,6,7}

8. Conversion from NFA to DFA 1 2 5 3 4 6 7 8 𝜖 a b 𝜖 a b 𝜖 𝜖 𝜖 𝜖 𝜖 𝜖 B= {1, 2, 3, 4, 6, 7, 8} Move(B,b) = {5,9} 𝜖- Closure( Move(B,b)) = {5, 6, 7, 1, 2, 4, 9} ---- D = {1,2,4,5,6,7,9} b 10 9 States a b A = {0,1,2,4,7} B C B = {1,2,3,4,6,7,8} B D C = {1,2,4,5,6,7} D = { 1,2,4,5,6,7,9 }

9. Conversion from NFA to DFA 1 2 5 3 4 6 7 8 𝜖 a b 𝜖 a b 𝜖 𝜖 𝜖 𝜖 𝜖 𝜖 Move(C,a) = {3,8} 𝜖- Closure( Move(C,a)) = {3, 6, 7, 1, 2, 4, 8} ---- B = {1,2,3,4,6,7,8} C= {1, 2, 4, 5, 6 ,7} b 10 9 States a b A = {0,1,2,4,7} B C B = {1,2,3,4,6,7,8} B D C = {1,2,4,5,6,7} B D = { 1,2,4,5,6,7,9 }

10. Conversion from NFA to DFA 1 2 5 3 4 6 7 8 𝜖 a b 𝜖 a b b 𝜖 𝜖 𝜖 𝜖 𝜖 𝜖 Move(C,b) = {5} 𝜖- Closure( Move(C,b))= {5, 6, 7, 1, 2, 4} ---- C = {1,2,4,5,6,7} C= {1, 2, 4, 5, 6, 7} 10 9 States a b A = {0,1,2,4,7} B C B = {1,2,3,4,6,7,8} B D C = {1,2,4,5,6,7} B C D = { 1,2,4,5,6,7,9 }

11. Conversion from NFA to DFA 1 2 5 3 4 6 7 8 𝜖 a b 𝜖 a b b 𝜖 𝜖 𝜖 𝜖 𝜖 𝜖 Move(D,a) = {3,8} 𝜖- Closure( Move(D,a)) = {3, 6, 7, 1, 2, 4, 8} ---- B = {1,2,3,4,6,7,8} D= {1, 2, 4, 5, 6, 7, 9} 10 9 States a b A = {0,1,2,4,7} B C B = {1,2,3,4,6,7,8} B D C = {1,2,4,5,6,7} B C D = { 1,2,4,5,6,7,9 } B

12. Conversion from NFA to DFA 1 2 5 3 4 6 7 8 𝜖 a b 𝜖 a b b 𝜖 𝜖 𝜖 𝜖 𝜖 𝜖 Move(D,b) = {5,10} 𝜖- Closure( Move(D,b)) = {5, 6, 7, 1, 2, 4, 10} ---- E = {1,2,4,5,6,7,10} D= {1, 2, 4, 5, 6, 7, 9} 10 9 States a b A = {0,1,2,4,7} B C B = {1,2,3,4,6,7,8} B D C = {1,2,4,5,6,7} B C D = { 1,2,4,5,6,7,9 } B E E = { 1,2,4,5,6,7,10 }

13. Conversion from NFA to DFA 1 2 5 3 4 6 7 8 𝜖 a b 𝜖 a b b 𝜖 𝜖 𝜖 𝜖 𝜖 𝜖 Move(E,a) = {3,8} 𝜖- Closure( Move(E,a)) = {3, 6, 7, 1, 2, 4, 8} ---- B = {1,2,3,4,6,7,8} E= {1, 2, 4, 5, 6, 7, 10} 10 9 States a b A = {0,1,2,4,7} B C B = {1,2,3,4,6,7,8} B D C = {1,2,4,5,6,7} B C D = { 1,2,4,5,6,7,9 } B E E = { 1,2,4,5,6,7,10 } B

14. Conversion from NFA to DFA 1 2 5 3 4 6 7 8 𝜖 a b 𝜖 a b b 𝜖 𝜖 𝜖 𝜖 𝜖 𝜖 Move(E,b)= {5} 𝜖- Closure( Move(E,b))= {5,6,7,1,2,4} ---- C = {1,2,4,5,6,7} States a b A = {0,1,2,4,7} B C B = {1,2,3,4,6,7,8} B D C = {1,2,4,5,6,7} B C E= {1, 2, 4, 5, 6, 7, 10} D = { 1,2,4,5,6,7,9 } B E E = { 1,2,4,5,6,7,10 } B C 10 9

15. Conversion from NFA to DFA       a b a b a     b a b b a Transition Table DFA Note: Accepting state in NFA is 10 10 is element of E So, E is acceptance state in DFA States a b A = {0,1,2,4,7} B C B = {1,2,3,4,6,7,8} B D C = {1,2,4,5,6,7} B C D = { 1,2,4,5,6,7,9 } B E E = { 1,2,4,5,6,7, 10 } B C

16. DFA optimization Construct an initial partition of the set of states with two groups: the accepting states and the non-accepting states . Apply the repartition procedure to to construct a new partition . If , let and continue with step (4). Otherwise, repeat step (2) with . for each group of do begin partition into subgroups such that two states and of are in the same subgroup if and only if for all input symbols , states and have transitions on to states in the same group of . replace in by the set of all subgroups formed. end  

17. DFA optimization Choose one state in each group of the partition as the representative for that group. The representatives will be the states of . Let s be a representative state, and suppose on input a there is a transition of from to . Let be the representative of s group. Then has a transition from to on . Let the start state of be the representative of the group containing start state of , and let the accepting states of be the representatives that are in . If has a dead state , then remove from . Also remove any state not reachable from the start state.  

18. DFA optimization Now no more splitting is possible. If we chose A as the representative for group (AC), then we obtain reduced transition table A B C B B D C B C D B E E B C States a b   Nonaccepting States   Accepting States         A B A B B D D B E E B A States a b Optimized Transition Table  

19. Rules to compute nullable, firstpos, lastpos nullable(n) The subtree at node generates languages including the empty string. firstpos(n) The set of positions that can match the first symbol of a string generated by the subtree at node lastpos(n) The set of positions that can match the last symbol of a string generated be the subtree at node followpos(i) The set of positions that can follow position in the tree.  

20. Rules to compute nullable, firstpos, lastpos Node n nullable(n) firstpos(n) lastpos(n) A leaf labeled by true true A leaf with position false false nullable(c 1 ) or nullable(c 2 ) firstpos(c 1 )  firstpos(c 2 ) lastpos(c 1 )  lastpos(c 2 ) nullable(c 1 ) and nullable(c 2 ) if (nullable(c 1 )) then firstpos(c 1 )  firstpos(c 2 ) else firstpos(c 1 ) if (nullable(c 2 )) then lastpos(c 1 )  lastpos(c 2 ) else lastpos(c 2 ) true firstpos(c 1 ) lastpos(c 1 )   n c 1 c 2 n   n   c 1 c 2 c 1

21. Rules to compute followpos If n is concatenation node with left child c1 and right child c2 and i is a position in lastpos(c1) , then all position in firstpos(c2) are in followpos(i) If n is * node and i is position in lastpos(n) , then all position in firstpos(n) are in followpos(i)

22. Conversion from regular expression to DFA         .       . . .       (a|b) * abb         # Step 2: Nullable node Here, * is only nullable node Step 1: Construct Syntax Tree

23. Conversion from regular expression to DFA         .               .     .     .           Step 3: Calculate firstpos Firstpos A leaf with position     n c 1 c 2 firstpos ( c 1 )  firstpos ( c 2 )   n c 1 firstpos ( c 1 )   n c 1 c 2             if ( nullable ( c 1 )) then firstpos ( c 1 )  firstpos ( c 2 ) else firstpos ( c 1 )

24. Conversion from regular expression to DFA         .                           .         .         .               Step 3: Calculate lastpos             Lastpos A leaf with position     n c 1 c 2 if ( nullable ( c 2 )) then lastpos ( c 1 )  lastpos ( c 2 ) else lastpos ( c 2 )   n c 1 lastpos ( c 1 )   n c 1 c 2 lastpos ( c 1 )  lastpos ( c 2 )

25. Conversion from regular expression to DFA Position followpos         .                           .         .         .               Step 4: Calculate followpos             5 6     .           Firstpos Lastpos

26. Conversion from regular expression to DFA Position followpos         .                           .         .         .               Step 4: Calculate followpos             5 6     .           4 5

27. Conversion from regular expression to DFA Position followpos         .                           .         .         .               Step 4: Calculate followpos             5 6     .           4 5 3 4 Firstpos Lastpos

28. Conversion from regular expression to DFA Position followpos         .                           .         .         .               Step 4: Calculate followpos             5 6     .         4 5 3 4 2 3 1 3 Firstpos Lastpos  

29. Conversion from regular expression to DFA Position followpos         .                           .         .         .               Step 4: Calculate followpos             5 6   4 5 3 4 2 3 1 3     * 1,2, 1,2, Firstpos Lastpos  

30. Conversion from regular expression to DFA Initial state = of root = {1,2,3} ----- A State A δ ( (1,2,3),a) = followpos(1) U followpos(3) =(1,2,3) U (4) = {1,2,3,4} ----- B δ ( (1,2,3),b) = followpos(2) =(1,2,3) ----- A   Position followpos 5 6 4 5 3 4 2 1,2,3 1 1,2,3 States a b A={1,2,3} B A B={1,2,3,4}

31. Conversion from regular expression to DFA State B δ ( (1,2,3,4),a) = followpos(1) U followpos(3) =(1,2,3) U (4) = {1,2,3,4} ----- B δ ( (1,2,3,4),b) = followpos(2) U followpos(4) =(1,2,3) U (5) = {1,2,3,5} ----- C State C δ ( (1,2,3,5),a) = followpos(1) U followpos(3) =(1,2,3) U (4) = {1,2,3,4} ----- B δ ( (1,2,3,5),b) = followpos(2) U followpos(5) =(1,2,3) U (6) = {1,2,3,6} ----- D Position followpos 5 6 4 5 3 4 2 1,2,3 1 1,2,3 States a b A={1,2,3} B A B={1,2,3,4} B C C={1,2,3,5} B D D={1,2,3,6}

32. Conversion from regular expression to DFA State D δ ( (1,2,3,6),a) = followpos(1) U followpos(3) =(1,2,3) U (4) = {1,2,3,4} ----- B δ ( (1,2,3,6),b) = followpos(2) =(1,2,3) ----- A Position followpos 5 6 4 5 3 4 2 1,2,3 1 1,2,3 States a b A={1,2,3} B A B={1,2,3,4} B C C={1,2,3,5} B D D={1,2,3,6} B A A B C D a b b b a a b a DFA