Automata theory - RE to DFA Conversion

Regular expression, dfa, finite automata

1. Convert RE to DFA 1 a 2 b 4 5 6 c 7 𝜀 𝜀 𝜀 8 𝜀 9 𝜀 𝜀 𝜀 10 NFA States DFA State Next State a b c D states 𝜀 Transition table of DFA Given RE = ( ab+c )* Equivalent NFA- ε is:

2. Convert RE to DFA 𝜀 NFA States DFA State Next State a b c D states Transition table of DFA Initial state of NFA is {9} Ε -closure(9)={ 9,7,1,5,10 } ------ Where A is the initial state of DFA A

3. Mark state A 1 a 2 b 4 5 6 c 7 𝜀 𝜀 𝜀 8 𝜀 9 𝜀 𝜀 𝜀 10 NFA States DFA State Next State a b c {9,7,1,5,10} A    D states 𝜀 Next need to find transition of ( A,a ) ( A,b ) ( A,c )

4. Compute 𝜀 -closure(move(A, a)) 1 a 2 b 4 5 6 c 7 𝜀 𝜀 8 𝜀 𝜀 9 𝜀 𝜀 𝜀 10 NFA States DFA State Next State a b c {9,7,1,5,10} A D states 𝜀 δ ( A,a ) = δ ( ( 9,7,1,5,10),a) = {2} = Ε -closure(2) = {2} ------ B

5. Compute 𝜀 -closure(move(A, a)) 1 a 2 b 4 5 6 c 7 𝜀 𝜀 8 𝜀 𝜀 9 𝜀 𝜀 𝜀 10 NFA States DFA State Next State a b c {9,7,1,5,10} A B  {2} B  D states 𝜀 δ ( A,a ) = δ ( ( 9,7,1,5,10),a) = {2} Ε -closure(2) = {2} ------ B

6. Compute 𝜀 -closure(move(A, b)) 1 a 2 b 4 5 6 c 7 𝜀 𝜀 8 𝜀 𝜀 9 𝜀 𝜀 𝜀 10 NFA States DFA State Next State a b c {9,7,1,5,10} A B - {2} B D states 𝜀

7. Compute 𝜀 -closure(move(A, c)) 1 a 2 b 4 5 6 c 7 𝜀 𝜀 8 𝜀 𝜀 9 𝜀 𝜀 𝜀 10 NFA States DFA State Next State a b c {9,7,1,5,10} A B - {2} B D states 𝜀 δ ( A,c ) = δ ( ( 9,7,1,5,10),c) = {6} Ε -closure(6) = { 6,8,10,7,1,5 } ------ C 

8. Mark move(A, c)) C 1 a 2 b 4 5 6 c 7 𝜀 𝜀 8 𝜀 𝜀 9 𝜀 𝜀 𝜀 10 NFA States DFA State Next State a b c {9,7,1,5,10} A B - C {2} B {6,8,10,7,1,5} C D states 𝜀

9. Compute 𝜀 -closure(move(B, a)) 1 a 2 b 4 5 6 c 7 𝜀 𝜀 8 𝜀 𝜀 9 𝜀 𝜀 𝜀 10 NFA States DFA State Next State a b c {9,7,1,5,10} A B - C {2} B - {6,8,10,7,1,5} C D states 𝜀 

10. Compute 𝜀 -closure(move(B, b )) 1 a 2 b 4 5 6 c 7 𝜀 𝜀 8 𝜀 𝜀 9 𝜀 𝜀 𝜀 10 NFA States DFA State Next State a b c {9,7,1,5,10} A B - C {2} B - {6,8,10,7,1,5} C D states 𝜀 δ ( B,b ) = δ ( (2,b ) = {4} Ε -closure(4) = { 4,8,10,7,1,5 } ------ D 

11. Mark (move(B, b)) 1 a 2 b 4 5 6 c 7 𝜀 𝜀 8 𝜀 𝜀 9 𝜀 𝜀 𝜀 10 NFA States DFA State Next State a b c {9,7,1,5,10} A  B - C {2} B  - D {6,8,10,7,1,5} C {4,8,7,1,5,10} D D states 𝜀

12. Mark - (move(B, c)) 1 a 2 b 4 5 6 c 7 𝜀 𝜀 8 𝜀 𝜀 9 𝜀 𝜀 𝜀 10 NFA States DFA State Next State a b c {9,7,1,5,10} A B - C {2} B - D - {6,8,10,7,1,5} C {4,8,7,1,5,10} D D states 𝜀

13. Compute 𝜀 -closure(move(C, a)) 1 a 2 b 4 5 6 c 7 𝜀 𝜀 8 𝜀 𝜀 9 𝜀 𝜀 𝜀 10 NFA States DFA State Next State a b c {9,7,1,5,10} A B - C {2} B - D - {6,8,10,7,1,5} C B {4,8,7,1,5,10} D D states 𝜀 B δ ( C,a ) = δ ( ( 6,8,10,7,1,5)) ,a ) = {2} Ε -closure(2) = { 2 } ------

14. Mark (move(C, b)) 1 a 2 b 4 5 6 c 7 𝜀 𝜀 8 𝜀 𝜀 9 𝜀 𝜀 𝜀 10 NFA States DFA State Next State a b c {9,7,1,5,10} A B - C {2} B - D - {6,8,10,7,1,5} C B - {4,8,7,1,5,10} D D states 𝜀

15. Compute 𝜀 -closure(move(C, c )) 1 a 2 b 4 5 6 c 7 𝜀 𝜀 8 𝜀 𝜀 9 𝜀 𝜀 𝜀 10 NFA States DFA State Next State a b c {9,7,1,5,10} A B - C {2} B - D - {6,8,10,7,1,5} C B - {4,8,7,1,5,10} D D states 𝜀 δ ( C,c ) = δ ( ( 6,8,10,7,1,5)) ,a ) = {6} Ε -closure(6) = { 6,8,10,7,1,5 } ------ C

16. Mark (move(C, c)) 1 a 2 b 4 5 6 c 7 𝜀 𝜀 8 𝜀 𝜀 9 𝜀 𝜀 𝜀 10 NFA States DFA State Next State a b c {9,7,1,5,10} A B - C {2} B - D - {6,8,10,7,1,5} C B - C {4,8,7,1,5,10} D D states 𝜀

17. Compute 𝜀 -closure(move(D, a )) 1 a 2 b 4 5 6 c 7 𝜀 𝜀 8 𝜀 𝜀 9 𝜀 𝜀 𝜀 10 NFA States DFA State Next State a b c {9,7,1,5,10} A B - C {2} B - D - {6,8,10,7,1,5} C B - C {4,8,7,1,5,10} D D states 𝜀 δ ( D,a ) = δ ( ( 6,8,10,7,1,5)) ,a ) = {2} Ε -closure(2) = {2} ------ B

18. Mark (move(D, a)) 1 a 2 b 4 5 6 c 7 𝜀 𝜀 8 𝜀 𝜀 9 𝜀 𝜀 𝜀 10 NFA States DFA State Next State a b c {9,7,1,5,10} A B - C {2} B - D - {6,8,10,7,1,5} C B - C {4,8,7,1,5,10} D B D states 𝜀

19. Mark (move(D, b )) 1 a 2 b 4 5 6 c 7 𝜀 𝜀 8 𝜀 𝜀 9 𝜀 𝜀 𝜀 10 NFA States DFA State Next State a b c {9,7,1,5,10} A B - C {2} B - D - {6,8,10,7,1,5} C B - C {4,8,7,1,5,10} D B - D states 𝜀

20. Compute 𝜀 -closure(move(D, c )) 1 a 2 b 4 5 6 c 7 𝜀 𝜀 8 𝜀 𝜀 9 𝜀 𝜀 𝜀 10 NFA States DFA State Next State a b c {9,7,1,5,10} A B - C {2} B - D - {6,8,10,7,1,5} C B - C {4,8,7,1,5,10} D B D states 𝜀 C ( D,c ) = δ ( ( 4,8,7,1,5,10)) ,c ) = {6} Ε -closure(6) = { 6,8,10,7,1,5 } ------

21. M ark (move(D, c )) 1 a 2 b 4 5 6 c 7 𝜀 𝜀 8 𝜀 𝜀 9 𝜀 𝜀 𝜀 10 NFA States DFA State Next State a b c {9,7,1,5,10} A B - C {2} B - D - {6,8,10,7,1,5} C B - C {4,8,7,1,5,10} D B - C D states 𝜀

22. Resultant DFA is a B c a b A a D c C c Transition table Transition diagram is