DFA First Undefined Transition Finder

Description

Locate the first undefined step of a partial deterministic trace and retain its state and requested symbol.

A deterministic transition maps a state and one literal alphabet symbol to at most one next state. A partial table may leave some pairs undefined; a complete table defines every state/symbol pair. Tracing one word, exploring all graph paths and changing the accepting set are distinct operations. IDs and symbols use exact string identity.

Locate the first undefined step of a partial deterministic trace and retain its state and requested symbol.

When to use this tool

Use the first undefined step to diagnose why a word cannot continue through a partial transition table.

How to use the tool and how it works

Enter transitionsJson, start, symbols using the definitions below. Serialize JSON text fields in the decoded shape shown below.
Run the operation. Resolve input-format errors before interpreting an output.
Read result.undefinedAt, result.state, result.symbol, using the stated boundary, ordering, sign and absence conventions.

Follow deterministic transitions from start until input is exhausted or a key is missing. Return the first missing input index, the last reached state, and the requested symbol at that index.^[1]

Input field	Meaning and units	Accepted input
transitionsJson	JSON array of {from,symbol,to} literal string records, preserving transition indexes. Determinism is checked or audited as described above.	Text, at most 8,192 UTF-16 code units; narrower grammar/range rules also apply.
start	Literal starting state. Graph operations with a declared state bank require it to be present there.	Text, at most 8,192 UTF-16 code units; narrower grammar/range rules also apply.
symbols	Ordered input symbols to consume, each a literal string. This list is a word, not the declared alphabet.	Dense list of at most 128 literal strings, each at most 8,192 UTF-16 units.

These decoded structures show the examples inside JSON text fields. Supply their serialized JSON strings as input.

json

{
  "transitionsJson": [
    {
      "from": "a",
      "symbol": "x",
      "to": "b"
    },
    {
      "from": "b",
      "symbol": "x",
      "to": "b"
    }
  ]
}

Output field	Interpretation
result	Object containing the fields below.
result.undefinedAt	First input-symbol index with no transition, or null when all symbols were consumed.
result.state	Last reached state before an undefined step, or the final reached state after complete input.
result.symbol	Requested symbol at the first undefined input index, or null after a complete trace.

json

{
  "input": {
    "transitionsJson": "[{\"from\": \"a\", \"symbol\": \"x\", \"to\": \"b\"}, {\"from\": \"b\", \"symbol\": \"x\", \"to\": \"b\"}]",
    "start": "a",
    "symbols": [
      "x",
      "y"
    ]
  },
  "output": {
    "result": {
      "undefinedAt": 1,
      "state": "b",
      "symbol": "y"
    }
  }
}

Limitations and assumptions

On a complete trace undefinedAt and symbol are null, while state remains the last reached state. The state/alphabet universe is not separately declared by this tool.
Transition JSON is an array of {from,symbol,to} string records. Tools requiring a declared automaton use a nonempty distinct state bank and distinct alphabet, validate endpoints and symbols, and reject duplicate [from,symbol] keys. Trace-only tools validate keys without inferring a declared universe. No normalization or implicit sink is provided.
Every declared outer field is required and unknown outer fields are rejected. Strings and JSON text have size limits, lists are bounded to 128 entries, and JSON nesting/node counts are bounded. Tighter operation-specific bounds stated above take precedence.
Numeric outputs must remain finite and within safe-integer magnitude. Original record indexes and cell coordinates are zero-based; stated half-open ranges exclude their end.

Alternative or Complementary methods

Use endpoint and duplicate-key audits before transformations. Check completeness before complementing an accepting set, and preserve the declared alphabet, start-state convention and acceptance policy with exported tables.

References

Tool behavior and example: DFA First Undefined Transition Finder — tool.io

Similar or alternative tools

DFA Symbol Sequence State Trace
Trace a symbol sequence through a partial deterministic transition table with state and transition-index provenance.
DFA Single Symbol Step
Look up one exact state/symbol transition and return explicit null evidence when it is undefined.