Open cmsalser opened 1 year ago
While working with conversions between NFA's and DFA's, I noticed an issue where the starting state had changed from the corresponding NFA.
{ "_nfa": { "in": { "_transitions": {}, "accepting": false, "number": 1, "_epsilonClosure": {} }, "out": { "_transitions": {}, "accepting": true, "number": 2, "_epsilonClosure": {} }, "_transitionTable": { "1": { "a": [ 2 ], "ε*": [ 1, 2 ] }, "2": { "ε*": [ 2 ] } }, "_acceptingStates": {}, "_alphabet": {}, "_acceptingStateNumbers": {} }, "_acceptingStateNumbers": {}, "_originalTransitionTable": { "2": {}, "1,2": { "a": "2" } }, "_originalAcceptingStateNumbers": {}, "_transitionTable": { "1": {}, "2": { "a": 1 } } }
{ "_nfa": { "in": { "_transitions": {}, "accepting": false, "number": 1, "_epsilonClosure": {} }, "out": { "_transitions": {}, "accepting": true, "number": 6, "_epsilonClosure": {} }, "_transitionTable": { "1": { "ε*": [ 1, 2, 7 ] }, "2": { "a": [ 3 ], "ε*": [ 2 ] }, "3": { "ε*": [ 3, 4, 5 ] }, "4": { "ε*": [ 4, 5 ] }, "5": { "c": [ 6 ], "ε*": [ 5 ] }, "6": { "ε*": [ 6 ] }, "7": { "b": [ 8 ], "ε*": [ 7 ] }, "8": { "ε*": [ 8, 4, 5 ] } }, "_acceptingStates": {}, "_alphabet": {}, "_acceptingStateNumbers": {} }, "_acceptingStateNumbers": {}, "_originalTransitionTable": { "6": {}, "1,2,7": { "a": "3,4,5", "b": "8,4,5" }, "8,4,5": { "c": "6" }, "3,4,5": { "c": "6" } }, "_originalAcceptingStateNumbers": {}, "_transitionTable": { "1": {}, "2": { "a": 4, "b": 3 }, "3": { "c": 1 }, "4": { "c": 1 } } }
Description
While working with conversions between NFA's and DFA's, I noticed an issue where the starting state had changed from the corresponding NFA.
Cases
{ "_nfa": { "in": { "_transitions": {}, "accepting": false, "number": 1, "_epsilonClosure": {} }, "out": { "_transitions": {}, "accepting": true, "number": 2, "_epsilonClosure": {} }, "_transitionTable": { "1": { "a": [ 2 ], "ε*": [ 1, 2 ] }, "2": { "ε*": [ 2 ] } }, "_acceptingStates": {}, "_alphabet": {}, "_acceptingStateNumbers": {} }, "_acceptingStateNumbers": {}, "_originalTransitionTable": { "2": {}, "1,2": { "a": "2" } }, "_originalAcceptingStateNumbers": {}, "_transitionTable": { "1": {}, "2": { "a": 1 } } }{ "_nfa": { "in": { "_transitions": {}, "accepting": false, "number": 1, "_epsilonClosure": {} }, "out": { "_transitions": {}, "accepting": true, "number": 6, "_epsilonClosure": {} }, "_transitionTable": { "1": { "ε*": [ 1, 2, 7 ] }, "2": { "a": [ 3 ], "ε*": [ 2 ] }, "3": { "ε*": [ 3, 4, 5 ] }, "4": { "ε*": [ 4, 5 ] }, "5": { "c": [ 6 ], "ε*": [ 5 ] }, "6": { "ε*": [ 6 ] }, "7": { "b": [ 8 ], "ε*": [ 7 ] }, "8": { "ε*": [ 8, 4, 5 ] } }, "_acceptingStates": {}, "_alphabet": {}, "_acceptingStateNumbers": {} }, "_acceptingStateNumbers": {}, "_originalTransitionTable": { "6": {}, "1,2,7": { "a": "3,4,5", "b": "8,4,5" }, "8,4,5": { "c": "6" }, "3,4,5": { "c": "6" } }, "_originalAcceptingStateNumbers": {}, "_transitionTable": { "1": {}, "2": { "a": 4, "b": 3 }, "3": { "c": 1 }, "4": { "c": 1 } } }For the above NFAs, the starting state is 1, however when converting to DFA, the new start changes to 2.