Description
Complement the accepting-state set of an explicitly complete deterministic finite 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.
Complement the accepting-state set of an explicitly complete deterministic finite automaton.
When to use this tool
Use this accepting-set transform only after a declared deterministic automaton is complete over its alphabet.
How to use the tool and how it works
- Enter transitionsJson, states, alphabet, accepting 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.accepting, using the stated boundary, ordering, sign and absence conventions.
Validate declared states, alphabet, deterministic keys and accepting membership, and require a transition for every state/alphabet pair. Return declared states outside the original accepting set.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. |
| accepting | Explicit literal accepting-state IDs; full automaton operations require membership in states. | 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.accepting | Declared state-bank complement of the original accepting set. |
{
"input": {
"transitionsJson": "[{\"from\": \"a\", \"symbol\": \"x\", \"to\": \"b\"}, {\"from\": \"b\", \"symbol\": \"x\", \"to\": \"b\"}]",
"states": [
"a",
"b"
],
"alphabet": [
"x"
],
"accepting": [
"b"
]
},
"output": {
"result": {
"accepting": [
"a"
]
}
}
}Limitations and assumptions
- Complementing acceptance is valid only for a complete deterministic table over the stated alphabet. Partial tables are rejected; no sink is added, and the table/start convention is otherwise unchanged.
- 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
- DFA Alphabet Transition Completeness
List missing state/alphabet transition pairs in a declared deterministic automaton.
- DFA Dead State Partitioner
Partition declared states into states with a path to acceptance and dead states without such a path.