+++ Input NFA Number of states: 22 Input alphabet: {0,1} Start states: {0,12} Final states: {11,14,16,18,20,21} Transition function Delta(0,0) = {0,1} Delta(0,1) = {0,2} Delta(1,0) = {3} Delta(1,1) = {4} Delta(2,0) = {4} Delta(2,1) = {} Delta(3,0) = {5} Delta(3,1) = {6} Delta(4,0) = {6} Delta(4,1) = {} Delta(5,0) = {7} Delta(5,1) = {8} Delta(6,0) = {8} Delta(6,1) = {} Delta(7,0) = {9} Delta(7,1) = {10} Delta(8,0) = {10} Delta(8,1) = {} Delta(9,0) = {} Delta(9,1) = {11} Delta(10,0) = {11} Delta(10,1) = {} Delta(11,0) = {} Delta(11,1) = {} Delta(12,0) = {13} Delta(12,1) = {14} Delta(13,0) = {15} Delta(13,1) = {16} Delta(14,0) = {16} Delta(14,1) = {} Delta(15,0) = {17} Delta(15,1) = {18} Delta(16,0) = {18} Delta(16,1) = {} Delta(17,0) = {19} Delta(17,1) = {20} Delta(18,0) = {20} Delta(18,1) = {} Delta(19,0) = {} Delta(19,1) = {21} Delta(20,0) = {21} Delta(20,1) = {} Delta(21,0) = {} Delta(21,1) = {} +++ Converted DFA Number of states: 4194304 Input alphabet: {0,1} Start state: 4097 4128768 final states Transition function: Skipped +++ Reachable states: {5,19,21,75,83,85,299,331,339,341,683,1195,1323,1355,1363,1365,2731,3243,3371,3403,3411,3413,4097,8195,16389,32779,65555,65557,131115,262219,262227,262229,524459,1048875,1048907,1048915,1048917,2098347,2098475,2098507,2098515,2098517} +++ Reduced DFA after removing unreachable states Number of states: 42 Input alphabet: {0,1} Start state: 22 Final states: {16,17,18,19,20,21,24,26,27,29,30,31,33,34,35,36,37,38,39,40,41} Transition function a\p| 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 ---+------------------------------------------------------------------------------------------------------------------------------ 0 | 1 3 4 6 7 8 11 12 13 14 10 16 17 18 19 20 10 16 17 18 19 20 23 25 26 28 29 30 32 33 34 35 10 37 38 39 40 16 17 18 19 20 1 | 0 2 0 5 2 0 9 5 2 0 21 15 9 5 2 0 21 15 9 5 2 0 24 27 0 31 2 0 36 5 2 0 41 9 5 2 0 15 9 5 2 0 +++ Equivalent states Group 0: {0} Group 1: {1} Group 2: {2} Group 3: {3} Group 4: {4} Group 5: {5} Group 6: {6} Group 7: {7} Group 8: {8} Group 9: {9} Group 10: {10,22,23,25,28,32} Group 11: {11} Group 12: {12} Group 13: {13} Group 14: {14} Group 15: {15} Group 16: {16} Group 17: {17,37} Group 18: {18,33,38} Group 19: {19,29,34,39} Group 20: {20,26,30,35,40} Group 21: {21,24,27,31,36,41} +++ Reduced DFA after collapsing equivalent states Number of states: 22 Input alphabet: {0,1} Start state: 10 Final states: {16,17,18,19,20,21} Transition function a\p| 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 ---+------------------------------------------------------------------ 0 | 1 3 4 6 7 8 11 12 13 14 10 16 17 18 19 20 10 16 17 18 19 20 1 | 0 2 0 5 2 0 9 5 2 0 21 15 9 5 2 0 21 15 9 5 2 0