Description
Partition declared automaton states into states reachable from start and the remaining unreachable states.
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.
Partition declared automaton states into states reachable from start and the remaining unreachable states.
When to use this tool
Use the reachability partition to distinguish states available from start from declared but unreachable states.
How to use the tool and how it works
- Enter transitionsJson, states, alphabet, start 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.reachable, result.unreachable, using the stated boundary, ordering, sign and absence conventions.
Validate the deterministic partial table and a declared start state. Traverse outgoing transitions breadth first, then take the declared-state-bank complement of the reached states.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. |
| 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. |
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.reachable | Breadth-first reachable state inventory from start. |
| result.unreachable | Declared states absent from reachable, in original state-bank order. |
{
"input": {
"transitionsJson": "[{\"from\": \"a\", \"symbol\": \"x\", \"to\": \"b\"}, {\"from\": \"b\", \"symbol\": \"x\", \"to\": \"b\"}]",
"states": [
"a",
"b",
"c"
],
"alphabet": [
"x"
],
"start": "a"
},
"output": {
"result": {
"reachable": [
"a",
"b"
],
"unreachable": [
"c"
]
}
}
}Limitations and assumptions
- reachable follows breadth-first discovery in transition order; unreachable follows declared bank order. Reachability concerns graph paths, without restricting to a single supplied word.
- 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 Reachable State Inventory
List automaton states reachable from an explicit start in breadth-first discovery order.
- DFA Dead State Partitioner
Partition declared states into states with a path to acceptance and dead states without such a path.