7-NFA to Minimized DFA.pptx

NFA to DFA

1. NFA to Minimized DFA

2. RE to DFA To convert RE to NFA use – Thompson’s algorithm To convert NFA to DFA use – Subset Construction algorithm To minimize the obtained DFA use – Tabulation method (also called Mark/Reduce procedure)

3. Subset construction algorithm Step 1: Find the λ -closure of all the states Step 2: Let the λ -closure of the initial state be named as A Step 3: Now find the transitions of each input symbol on this state A. Then, find the λ -closure of the above set and name it as A if it appears to be same otherwise give a new name as B. Step 4: Repeat Step 3 for each of the new states added until there are no new states in the queue. Step 5: Convert the above representation to a DFA. The initial state of the DFA will be A. Mark the final states of DFA.

4. Example 1 Convert the RE ( a+b )* abb to a minimized DFA λ -closure(0) = {0, 1, 2, 4, 7} λ -closure(4) = {4} λ -closure(8) = {8} λ -closure(1) = {1, 2, 4} λ -closure(5) = {1, 2, 4, 5, 6, 7} λ -closure(9) = {9} λ -closure(2) = {2} λ -closure(6) = {1, 2, 4, 6, 7} λ -closure(10) = {10} λ -closure(3) = {1, 2, 3, 4, 6, 7} λ -closure(7) = {7}

5. Example 1 λ -closure(0) = {0, 1, 2, 4, 7} – A λ -closure(ẟ(A, a)) = λ -closure(3, 8) = {1, 2, 3, 4, 6, 7, 8} – B λ -closure(ẟ(A, b)) = λ -closure(5) = {1, 2, 4, 5, 6, 7} – C λ -closure(ẟ(B, a)) = λ -closure(3, 8) = {1, 2, 3, 4, 6, 7, 8} – B λ -closure(ẟ(B, b)) = λ -closure(5, 9) = {1, 2, 4, 5, 6, 7, 9} – D λ -closure(ẟ(C, a)) = λ -closure(3, 8) = {1, 2, 3, 4, 6, 7, 8} – B λ -closure(ẟ(C, b )) = λ -closure(5) = {1, 2, 4, 5, 6 , 7 } – C λ -closure(ẟ(D, a)) = λ -closure(3, 8) = {1, 2, 3, 4, 6, 7, 8} – B λ -closure(ẟ(D, b )) = λ -closure(5, 10 ) = {1, 2, 4, 5, 6, 7, 10} – E λ -closure(ẟ(E, a)) = λ -closure(3, 8) = {1, 2, 3, 4, 6, 7, 8} – B λ -closure(ẟ(E, b )) = λ -closure(5) = {1, 2, 4, 5, 6, 7} – C

6. Example 1 – Final DFA States a b -> A B C B B D C B C D B E * E B C A B C D E E a a a a a b b b b b

7. DFA Minimization – Tabulation Method States a b -> A B C B B D C B C D B E * E B C B C D E A B C D Mark/Reduce Procedure Pair – (AC)

8. Minimized DFA States a b -> A B C B B D C B C D B E * E B C States a b -> A B A B B D D B E * E B A A B D E E b b b b a a a a

9. Mark/Reduce Procedure

10. Example 2 Find the minimal DFA for abb ( a+b )*

11. Example 2 λ -closure(0) = {0} λ -closure(1) = {1} λ -closure(2) = {2} λ -closure(3) = {3, 4, 5, 7, 10} λ -closure(4) = {4, 5, 7} λ -closure(5) = {5} λ -closure(6) = {4, 5, 6, 7, 9, 10} λ -closure(7) = {7} λ -closure(8) = {4, 5, 7, 8, 9, 10} λ -closure(9) = {4, 5, 7, 9, 10} λ -closure(10) = {10}

12. Example 2 – Subset Alg. λ -closure(0) = {0} - A λ -closure(ẟ(A, a)) = λ -closure(1) = {1} – B λ -closure(ẟ(A, b)) = φ λ -closure(ẟ(B, a)) = φ λ -closure(ẟ(B, b )) = λ -closure(2) = {2} – C λ -closure(ẟ(C, a)) = φ λ -closure(ẟ(C, b )) = λ -closure(3) = {3, 4, 5, 7, 10} – D

13. Example 2 λ -closure(ẟ(D, a)) = λ -closure(6) = {4, 5, 6, 7, 9, 10} – E λ -closure(ẟ(D, b )) = λ -closure(8) = {4, 5, 7, 8, 9, 10} – F λ -closure(ẟ(E, a)) = λ -closure(6) = {4, 5, 6, 7, 9, 10} – E λ -closure(ẟ(E, b )) = λ -closure(8) = {4, 5, 7, 8, 9, 10} – F λ -closure(ẟ(F, a)) = λ -closure(6) = {4, 5, 6, 7, 9, 10} – E λ -closure(ẟ(F, b )) = λ -closure(8) = {4, 5, 7, 8, 9, 10} – F

14. Example 2 - Minimization States a b -> A B φ B φ C C φ D * D E F * E E F * F E F B C D E F A B C D E Pairs {{DE}{DF}} {EF} => {DEF}

15. Example 2 – Minimized DFA States a b -> A B φ B φ C C φ D * D D D A B C D D T a b a b a b a, b a, b

16. Example 3 Convert to minimized DFA λ -closure(q0) = {q0} λ -closure(q1) = {q1} λ -closure(q2) = {q2} q0 q1 q1 q2 0, 1 0, 1 1

17. Example 3 λ -closure(q0) = {q0} – A λ -closure(ẟ(A, )) = λ -closure(q0,q1} = {q0,q1} – B λ -closure(ẟ(A, 1)) = λ -closure(q1} = {q1} – C λ -closure(ẟ(B, )) = λ -closure(q0,q1,q2} = {q0,q1,q2} – D λ -closure(ẟ(B, 1)) = λ -closure(q1,q2} = {q1,q2} – E λ -closure(ẟ(C, )) = λ -closure(q2} = {q2} – F λ -closure(ẟ(C, 1)) = λ -closure(q2} = {q2} – F λ -closure(ẟ(D, )) = λ -closure(q0,q1,q2} = {q0,q1,q2} – D λ -closure(ẟ(D, 1)) = λ -closure(q1,q2} = {q1,q2} - E

18. Example 3 λ -closure(ẟ(E, )) = λ -closure(q2} = {q2} – F λ -closure(ẟ(E, 1)) = λ -closure(q2} = {q2} – F λ -closure(ẟ(F, )) = φ λ -closure(ẟ(F, 1)) = λ -closure(q2} = {q2} - F States 1 -> A B C *B D E *C F F *D D E *E F F F φ F

19. Example 3 B C D E F A B C D E States 1 -> A B C *B D E *C F F *D D E *E F F F φ F Pairs: (BD), (CE)

20. Example 3 – Minimized DFA Let (BD) be X Let (CE) be Y States 1 -> A B C *B D E *C F F *D D E *E F F F φ F States 1 -> A X Y *X X Y *Y F F F φ F A X Y F X Y 1 1 0, 1 0, 1

21. Example 4 Find the minimized DFA for the given NFA λ -closure(q0) = {q0, q1} λ -closure(q1) = {q1} λ -closure(q2) = {q2} q0 q1 q2 q1 0, λ 1 0, 1 1

22. Example 4 λ -closure(q0) = {q0, q1} - A λ -closure(ẟ(A, )) = λ -closure(q0, q1, q2) = {q0, q1, q2} – B λ -closure(ẟ(A, 1)) = λ -closure(q1, q2) = {q1, q2} – C λ -closure(ẟ(B, )) = λ -closure(q0, q1, q2) = {q0, q1, q2} – B λ -closure(ẟ(B, 1)) = λ -closure(q1, q2) = {q1, q2} – C λ -closure(ẟ(C, )) = λ -closure(q0, q2) = {q0, q1, q2} – B λ -closure(ẟ(C, 1)) = λ -closure(q1, q2) = {q1, q2} - C

23. Example 4 B C A B States 1 ->* A B C *B B C *C B C All pairs are indistinguishable So, {ABC} is a single state X X 0, 1

24. Example 5 - Minimize the given DFA First draw the DFA and check if all the states are reachable from start state The sets are {q1, q2, q3} and {q2, q3}. So, {q1, q2, q3} can be combined into one state States 1 -> q0 q1 q3 q1 q2 q4 q2 q1 q4 q3 q2 q4 *q4 q4 q4 q1 q2 q3 q4 q0 q1 q2 q3 States 1 -> q0 X X X X q4 *q4 q4 q4

25. Exercises – NFA to Minimized DFA 1. 2. A B X C a b c λ λ A B C B 1 0,1 0,1

26. Exercises – NFA to Minimized DFA 3. 4. RE ab*a( a+b ) 5. RE (0+1)+(0+1)* 6. 7.   A B X C a b a, b a, λ b, λ b, λ

27. Exercises – Minimize the DFA 8. 9. States 1 -> A B F B G C *C A C D C G E H F F C G G G E H G C

28. Exercises 10.