ERROR when converting from Ɛ-NFA to DFA

[aboqasem]

Hi! I am getting an unexpected outcome when converting from eNFA to DFA (Codeandbox):

const enfa = {
    "states": [
        "s0",
        "s1",
        "s2",
        "s3"
    ],
    "alphabet": [
        "a",
        "b",
        "c"
    ],
    "initialState": "s0",
    "acceptingStates": [
        "s2"
    ],
    "transitions": [
        {
            "fromState": "s0",
            "symbol": "a",
            "toStates": [
                "s0"
            ]
        },
        {
            "fromState": "s0",
            "symbol": "b",
            "toStates": [
                "s0",
                "s2"
            ]
        },
        {
            "fromState": "s0",
            "symbol": "c",
            "toStates": [
                "s0",
                "s2"
            ]
        },
        {
            "fromState": "s0",
            "symbol": "δ",
            "toStates": [
                "s1",
                "s2"
            ]
        },
        {
            "fromState": "s1",
            "symbol": "a",
            "toStates": [
                "s3"
            ]
        },
        {
            "fromState": "s1",
            "symbol": "c",
            "toStates": [
                "s2"
            ]
        },
        {
            "fromState": "s2",
            "symbol": "c",
            "toStates": [
                "s2",
                "s3"
            ]
        },
        {
            "fromState": "s2",
            "symbol": "δ",
            "toStates": [
                "s3"
            ]
        },
        {
            "fromState": "s3",
            "symbol": "δ",
            "toStates": [
                "s0",
                "s3"
            ]
        }
    ]
};

const nfa = noam.fsm.convertEnfaToNfa(enfa);
// {
//     "states": [
//         "s0",
//         "s1",
//         "s2",
//         "s3"
//     ],
//     "alphabet": [
//         "a",
//         "b",
//         "c"
//     ],
//     "initialState": "s0",
//     "acceptingStates": [
//         "s2"
//     ],
//     "transitions": [
//         {
//             "fromState": "s0",
//             "symbol": "a",
//             "toStates": [
//                 "s0"
//             ]
//         },
//         {
//             "fromState": "s0",
//             "symbol": "b",
//             "toStates": [
//                 "s0",
//                 "s2"
//             ]
//         },
//         {
//             "fromState": "s0",
//             "symbol": "c",
//             "toStates": [
//                 "s0",
//                 "s2"
//             ]
//         },
//         {
//             "fromState": "s0",
//             "symbol": "δ",
//             "toStates": [
//                 "s1",
//                 "s2"
//             ]
//         },
//         {
//             "fromState": "s1",
//             "symbol": "a",
//             "toStates": [
//                 "s3"
//             ]
//         },
//         {
//             "fromState": "s1",
//             "symbol": "c",
//             "toStates": [
//                 "s2"
//             ]
//         },
//         {
//             "fromState": "s2",
//             "symbol": "c",
//             "toStates": [
//                 "s2",
//                 "s3"
//             ]
//         },
//         {
//             "fromState": "s2",
//             "symbol": "δ",
//             "toStates": [
//                 "s3"
//             ]
//         },
//         {
//             "fromState": "s3",
//             "symbol": "δ",
//             "toStates": [
//                 "s0",
//                 "s3"
//             ]
//         }
//     ]
// }


const dfa = noam.fsm.convertNfaToDfa(nfa);
// {
//     "alphabet": [
//         "a",
//         "b",
//         "c"
//     ],
//     "states": [
//         [
//             "s0"
//         ],
//         [
//             "s1"
//         ],
//         [
//             "s2"
//         ],
//         [
//             "s3"
//         ],
//         [
//             "s0",
//             "s3"
//         ],
//         [
//             "s2",
//             "s3"
//         ],
//         [
//             "s1",
//             "s2"
//         ],
//         [
//             "s0",
//             "s2"
//         ],
//         [
//             "s0",
//             "s2",
//             "s3"
//         ],
//         [
//             "ERROR"
//         ]
//     ],
//     "acceptingStates": [
//         [
//             "s2"
//         ],
//         [
//             "s2",
//             "s3"
//         ],
//         [
//             "s1",
//             "s2"
//         ],
//         [
//             "s0",
//             "s2"
//         ],
//         [
//             "s0",
//             "s2",
//             "s3"
//         ]
//     ],
//     "initialState": [
//         "s0"
//     ],
//     "transitions": [
//         {
//             "fromState": [
//                 "s0"
//             ],
//             "symbol": "a",
//             "toStates": [
//                 [
//                     "s0"
//                 ]
//             ]
//         },
//         {
//             "fromState": [
//                 "s0"
//             ],
//             "symbol": "b",
//             "toStates": [
//                 [
//                     "s0",
//                     "s2"
//                 ]
//             ]
//         },
//         {
//             "fromState": [
//                 "s0"
//             ],
//             "symbol": "c",
//             "toStates": [
//                 [
//                     "s0",
//                     "s2"
//                 ]
//             ]
//         },
//         {
//             "fromState": [
//                 "s0"
//             ],
//             "symbol": "δ",
//             "toStates": [
//                 [
//                     "s1",
//                     "s2"
//                 ]
//             ]
//         },
//         {
//             "fromState": [
//                 "s1"
//             ],
//             "symbol": "a",
//             "toStates": [
//                 [
//                     "s3"
//                 ]
//             ]
//         },
//         {
//             "fromState": [
//                 "s1"
//             ],
//             "symbol": "c",
//             "toStates": [
//                 [
//                     "s2"
//                 ]
//             ]
//         },
//         {
//             "fromState": [
//                 "s2"
//             ],
//             "symbol": "c",
//             "toStates": [
//                 [
//                     "s2",
//                     "s3"
//                 ]
//             ]
//         },
//         {
//             "fromState": [
//                 "s2"
//             ],
//             "symbol": "δ",
//             "toStates": [
//                 [
//                     "s3"
//                 ]
//             ]
//         },
//         {
//             "fromState": [
//                 "s3"
//             ],
//             "symbol": "δ",
//             "toStates": [
//                 [
//                     "s0",
//                     "s3"
//                 ]
//             ]
//         },
//         {
//             "fromState": [
//                 "s0",
//                 "s3"
//             ],
//             "symbol": "a",
//             "toStates": [
//                 [
//                     "s0"
//                 ]
//             ]
//         },
//         {
//             "fromState": [
//                 "s0",
//                 "s3"
//             ],
//             "symbol": "b",
//             "toStates": [
//                 [
//                     "s0",
//                     "s2"
//                 ]
//             ]
//         },
//         {
//             "fromState": [
//                 "s0",
//                 "s3"
//             ],
//             "symbol": "c",
//             "toStates": [
//                 [
//                     "s0",
//                     "s2"
//                 ]
//             ]
//         },
//         {
//             "fromState": [
//                 "s2",
//                 "s3"
//             ],
//             "symbol": "c",
//             "toStates": [
//                 [
//                     "s2",
//                     "s3"
//                 ]
//             ]
//         },
//         {
//             "fromState": [
//                 "s1",
//                 "s2"
//             ],
//             "symbol": "a",
//             "toStates": [
//                 [
//                     "s3"
//                 ]
//             ]
//         },
//         {
//             "fromState": [
//                 "s1",
//                 "s2"
//             ],
//             "symbol": "c",
//             "toStates": [
//                 [
//                     "s2",
//                     "s3"
//                 ]
//             ]
//         },
//         {
//             "fromState": [
//                 "s0",
//                 "s2"
//             ],
//             "symbol": "a",
//             "toStates": [
//                 [
//                     "s0"
//                 ]
//             ]
//         },
//         {
//             "fromState": [
//                 "s0",
//                 "s2"
//             ],
//             "symbol": "b",
//             "toStates": [
//                 [
//                     "s0",
//                     "s2"
//                 ]
//             ]
//         },
//         {
//             "fromState": [
//                 "s0",
//                 "s2"
//             ],
//             "symbol": "c",
//             "toStates": [
//                 [
//                     "s0",
//                     "s2",
//                     "s3"
//                 ]
//             ]
//         },
//         {
//             "fromState": [
//                 "s0",
//                 "s2",
//                 "s3"
//             ],
//             "symbol": "a",
//             "toStates": [
//                 [
//                     "s0"
//                 ]
//             ]
//         },
//         {
//             "fromState": [
//                 "s0",
//                 "s2",
//                 "s3"
//             ],
//             "symbol": "b",
//             "toStates": [
//                 [
//                     "s0",
//                     "s2"
//                 ]
//             ]
//         },
//         {
//             "fromState": [
//                 "s0",
//                 "s2",
//                 "s3"
//             ],
//             "symbol": "c",
//             "toStates": [
//                 [
//                     "s0",
//                     "s2",
//                     "s3"
//                 ]
//             ]
//         },
//         {
//             "fromState": [
//                 "s1"
//             ],
//             "symbol": "b",
//             "toStates": [
//                 [
//                     "ERROR"
//                 ]
//             ]
//         },
//         {
//             "fromState": [
//                 "s2"
//             ],
//             "symbol": "a",
//             "toStates": [
//                 [
//                     "ERROR"
//                 ]
//             ]
//         },
//         {
//             "fromState": [
//                 "s2"
//             ],
//             "symbol": "b",
//             "toStates": [
//                 [
//                     "ERROR"
//                 ]
//             ]
//         },
//         {
//             "fromState": [
//                 "s3"
//             ],
//             "symbol": "a",
//             "toStates": [
//                 [
//                     "ERROR"
//                 ]
//             ]
//         },
//         {
//             "fromState": [
//                 "s3"
//             ],
//             "symbol": "b",
//             "toStates": [
//                 [
//                     "ERROR"
//                 ]
//             ]
//         },
//         {
//             "fromState": [
//                 "s3"
//             ],
//             "symbol": "c",
//             "toStates": [
//                 [
//                     "ERROR"
//                 ]
//             ]
//         },
//         {
//             "fromState": [
//                 "s2",
//                 "s3"
//             ],
//             "symbol": "a",
//             "toStates": [
//                 [
//                     "ERROR"
//                 ]
//             ]
//         },
//         {
//             "fromState": [
//                 "s2",
//                 "s3"
//             ],
//             "symbol": "b",
//             "toStates": [
//                 [
//                     "ERROR"
//                 ]
//             ]
//         },
//         {
//             "fromState": [
//                 "s1",
//                 "s2"
//             ],
//             "symbol": "b",
//             "toStates": [
//                 [
//                     "ERROR"
//                 ]
//             ]
//         },
//         {
//             "fromState": [
//                 "ERROR"
//             ],
//             "symbol": "a",
//             "toStates": [
//                 [
//                     "ERROR"
//                 ]
//             ]
//         },
//         {
//             "fromState": [
//                 "ERROR"
//             ],
//             "symbol": "b",
//             "toStates": [
//                 [
//                     "ERROR"
//                 ]
//             ]
//         },
//         {
//             "fromState": [
//                 "ERROR"
//             ],
//             "symbol": "c",
//             "toStates": [
//                 [
//                     "ERROR"
//                 ]
//             ]
//         }
//     ]
// }

[izuzak]

👋 @aboqasem Thanks for opening an issue! Can you please clarify why exactly you believe the output is unexpected?

If it's the presence of the ERROR state, then that's actually expected. The ERROR state is used for when the automaton receives an input character for which there is no defined transition in the current state. If there's no defined transition for that character, then the automaton goes into an ERROR state and stays there regardless of what inputs are received next. In other words, the automaton received invalid/unexpected input and it stays in an ERROR state because of that.

[aboqasem]

Thank you for your response! I thought a valid ENFA would always result in a valid DFA, I have no problems otherwise. Closing this issue then. Thank you and take care!