Description
List missing state/alphabet transition pairs in a declared deterministic automaton.
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.
List missing state/alphabet transition pairs in a declared deterministic automaton.
When to use this tool
Use completeness evidence before any operation that depends on a transition for every state/symbol pair.
How to use the tool and how it works
- Enter transitionsJson, states, alphabet 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.missing, using the stated boundary, ordering, sign and absence conventions.
Validate state and alphabet membership and unique transition keys. For every state/alphabet pair, report it if no transition is defined, preserving state-then-alphabet bank order.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. |
| states | Distinct literal declared state IDs in bank order; full automaton operations require at least one. | Dense list of at most 128 literal strings, each at most 8,192 UTF-16 units. |
| alphabet | Distinct literal alphabet symbols in bank order; an empty alphabet is allowed. | 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.
{
"transitionsJson": [
{
"from": "a",
"symbol": "x",
"to": "b"
},
{
"from": "b",
"symbol": "x",
"to": "b"
}
]
}| Output field | Interpretation |
|---|---|
| result | Object containing the fields below. |
| result.missing | Missing endpoint or state/symbol evidence with the original indexes or bank ordering described above. |
{
"input": {
"transitionsJson": "[{\"from\": \"a\", \"symbol\": \"x\", \"to\": \"b\"}, {\"from\": \"b\", \"symbol\": \"x\", \"to\": \"b\"}]",
"states": [
"a",
"b",
"c"
],
"alphabet": [
"x"
]
},
"output": {
"result": {
"missing": [
{
"state": "c",
"symbol": "x"
}
]
}
}
}Limitations and assumptions
- No missing transition or sink state is inserted. Empty alphabets have no required pairs; endpoint coverage and determinism errors are rejected before the completeness report.
- 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
Similar or alternative tools
- Complete DFA Acceptance Complement Set
Complement the accepting-state set of an explicitly complete deterministic finite automaton.
- DFA Deterministic Transition Key Audit
Audit repeated deterministic state/symbol transition keys, including identical duplicate records.