Autograder arbitrarily kills itself

[deep-goyal]

There have been multiple instances where Gradescope just kills the auto-grader instance after submitting a perfectly fine JSON file. Here is one such file:

{"dfa": {}, "nfa": {"1": {"type": "nfa", "states": ["q_0", "q_2", "q_3", "q_4", "q_1"], "input_symbols": ["0", "1"], "finals": ["q_4"], "start_state": "q_0", "delta": [{"from": "q_0", "to": ["q_0"], "input": "0"}, {"from": "q_0", "to": ["q_0", "q_1"], "input": "1"}, {"from": "q_1", "to": ["q_2"], "input": "0"}, {"from": "q_2", "to": ["q_3"], "input": "1"}, {"from": "q_3", "to": ["q_4"], "input": "0"}, {"from": "q_4", "to": ["q_4"], "input": "0"}, {"from": "q_4", "to": ["q_4"], "input": "1"}], "epsilon_char": "_"}, "2": {"type": "nfa", "states": ["q_0", "q_1"], "input_symbols": ["0", "1"], "finals": ["q_1"], "start_state": "q_0", "delta": [{"from": "q_0", "to": ["q_1"], "input": "0"}, {"from": "q_0", "to": ["q_1"], "input": "1"}, {"from": "q_1", "to": ["q_1"], "input": "0"}, {"from": "q_1", "to": ["q_1"], "input": "1"}], "epsilon_char": "_"}, "3": {"type": "nfa", "states": ["q_2", "q_1", "q_0", "q_3"], "input_symbols": ["b", "a"], "finals": ["q_3"], "start_state": "q_0", "delta": [{"from": "q_0", "to": ["q_0", "q_1"], "input": "a"}, {"from": "q_0", "to": ["q_1"], "input": "b"}, {"from": "q_1", "to": ["q_2"], "input": "b"}, {"from": "q_2", "to": ["q_3"], "input": "a"}, {"from": "q_2", "to": ["q_2"], "input": "b"}, {"from": "q_3", "to": ["q_3"], "input": "a"}, {"from": "q_3", "to": ["q_3"], "input": "b"}], "epsilon_char": "_"}, "4": {"type": "nfa", "states": ["q_2", "q_1", "q_0"], "input_symbols": ["b", "a", "c"], "finals": ["q_0", "q_1"], "start_state": "q_0", "delta": [{"from": "q_0", "to": ["q_0", "q_1"], "input": "a"}, {"from": "q_0", "to": ["q_0", "q_1"], "input": "c"}, {"from": "q_0", "to": ["q_1"], "input": "b"}, {"from": "q_1", "to": ["q_2"], "input": "a"}, {"from": "q_1", "to": ["q_2"], "input": "b"}, {"from": "q_1", "to": ["q_2"], "input": "c"}, {"from": "q_2", "to": ["q_2"], "input": "a"}, {"from": "q_2", "to": ["q_2"], "input": "b"}, {"from": "q_2", "to": ["q_2"], "input": "c"}], "epsilon_char": "_"}, "5": {"type": "nfa", "states": ["q_5", "q_0", "q_2", "q_3", "q_4", "q_1"], "input_symbols": ["0", "1"], "finals": ["q_1", "q_3"], "start_state": "q_0", "delta": [{"from": "q_0", "to": ["q_1"], "input": "0"}, {"from": "q_0", "to": ["q_1"], "input": "1"}, {"from": "q_1", "to": ["q_1"], "input": "0"}, {"from": "q_1", "to": ["q_1"], "input": "1"}, {"from": "q_1", "to": ["q_2"], "input": "_"}, {"from": "q_2", "to": ["q_3"], "input": "1"}, {"from": "q_3", "to": ["q_3"], "input": "0"}, {"from": "q_3", "to": ["q_4"], "input": "1"}, {"from": "q_4", "to": ["q_4"], "input": "0"}, {"from": "q_4", "to": ["q_3"], "input": "1"}], "epsilon_char": "_"}}, "pda": {}}

The NFAs in this file are perfectly fine and are mostly correct. They should not cause any parsing error. Here is what I get:

Killed

Your results.json file could not be parsed as JSON. Its contents are as follows:

What's interesting is that the submitted file is called submissions.json and yet the output mentions a results.json.

Here is the same file formatted:

{
  "dfa": {},
  "nfa": {
    "1": {
      "type": "nfa",
      "states": ["q_0", "q_2", "q_3", "q_4", "q_1"],
      "input_symbols": ["0", "1"],
      "finals": ["q_4"],
      "start_state": "q_0",
      "delta": [
        { "from": "q_0", "to": ["q_0"], "input": "0" },
        { "from": "q_0", "to": ["q_0", "q_1"], "input": "1" },
        { "from": "q_1", "to": ["q_2"], "input": "0" },
        { "from": "q_2", "to": ["q_3"], "input": "1" },
        { "from": "q_3", "to": ["q_4"], "input": "0" },
        { "from": "q_4", "to": ["q_4"], "input": "0" },
        { "from": "q_4", "to": ["q_4"], "input": "1" }
      ],
      "epsilon_char": "_"
    },
    "2": {
      "type": "nfa",
      "states": ["q_0", "q_1"],
      "input_symbols": ["0", "1"],
      "finals": ["q_1"],
      "start_state": "q_0",
      "delta": [
        { "from": "q_0", "to": ["q_1"], "input": "0" },
        { "from": "q_0", "to": ["q_1"], "input": "1" },
        { "from": "q_1", "to": ["q_1"], "input": "0" },
        { "from": "q_1", "to": ["q_1"], "input": "1" }
      ],
      "epsilon_char": "_"
    },
    "3": {
      "type": "nfa",
      "states": ["q_2", "q_1", "q_0", "q_3"],
      "input_symbols": ["b", "a"],
      "finals": ["q_3"],
      "start_state": "q_0",
      "delta": [
        { "from": "q_0", "to": ["q_0", "q_1"], "input": "a" },
        { "from": "q_0", "to": ["q_1"], "input": "b" },
        { "from": "q_1", "to": ["q_2"], "input": "b" },
        { "from": "q_2", "to": ["q_3"], "input": "a" },
        { "from": "q_2", "to": ["q_2"], "input": "b" },
        { "from": "q_3", "to": ["q_3"], "input": "a" },
        { "from": "q_3", "to": ["q_3"], "input": "b" }
      ],
      "epsilon_char": "_"
    },
    "4": {
      "type": "nfa",
      "states": ["q_2", "q_1", "q_0"],
      "input_symbols": ["b", "a", "c"],
      "finals": ["q_0", "q_1"],
      "start_state": "q_0",
      "delta": [
        { "from": "q_0", "to": ["q_0", "q_1"], "input": "a" },
        { "from": "q_0", "to": ["q_0", "q_1"], "input": "c" },
        { "from": "q_0", "to": ["q_1"], "input": "b" },
        { "from": "q_1", "to": ["q_2"], "input": "a" },
        { "from": "q_1", "to": ["q_2"], "input": "b" },
        { "from": "q_1", "to": ["q_2"], "input": "c" },
        { "from": "q_2", "to": ["q_2"], "input": "a" },
        { "from": "q_2", "to": ["q_2"], "input": "b" },
        { "from": "q_2", "to": ["q_2"], "input": "c" }
      ],
      "epsilon_char": "_"
    },
    "5": {
      "type": "nfa",
      "states": ["q_5", "q_0", "q_2", "q_3", "q_4", "q_1"],
      "input_symbols": ["0", "1"],
      "finals": ["q_1", "q_3"],
      "start_state": "q_0",
      "delta": [
        { "from": "q_0", "to": ["q_1"], "input": "0" },
        { "from": "q_0", "to": ["q_1"], "input": "1" },
        { "from": "q_1", "to": ["q_1"], "input": "0" },
        { "from": "q_1", "to": ["q_1"], "input": "1" },
        { "from": "q_1", "to": ["q_2"], "input": "_" },
        { "from": "q_2", "to": ["q_3"], "input": "1" },
        { "from": "q_3", "to": ["q_3"], "input": "0" },
        { "from": "q_3", "to": ["q_4"], "input": "1" },
        { "from": "q_4", "to": ["q_4"], "input": "0" },
        { "from": "q_4", "to": ["q_3"], "input": "1" }
      ],
      "epsilon_char": "_"
    }
  },
  "pda": {}
}

Here are are some ambiguities I noticed:

1. In Q5, there is an extra state q_5 that ends up not being used in any transitions.

I removed this extra state, plugged the JSON file back in, and the auto-grader completed execution and produced the expected output. BUT, running it again produced a completely different timeout error:

Your submission timed out. It took longer than 600 seconds to run.

2. This is extremely unlikely to cause a problem, but most submissions that fail like this also have a pattern of having a self-looping transition on all input symbols and then an epsilon transition to a different state. Something like this:

{ "from": "q_1", "to": ["q_1"], "input": "0" },
{ "from": "q_1", "to": ["q_1"], "input": "1" },
{ "from": "q_1", "to": ["q_2"], "input": "_" },