DFA State Renaming Transform

Description

Apply an injective state renaming to a validated deterministic transition table.

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.

Apply an injective state renaming to a validated deterministic transition table.

When to use this tool

Use state renaming to relabel a declared automaton while preserving its transition structure.

How to use the tool and how it works

Enter transitionsJson, states, alphabet, names, replacements 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.states, result.alphabet, result.transitions, using the stated boundary, ordering, sign and absence conventions.

Validate the deterministic state/alphabet table and a mapping of distinct known state names to aligned replacements. Apply it once to the state bank and both endpoints of every transition.^[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.
names	Distinct existing state or alphabet IDs to rename, as specified by the operation.	Dense list of at most 128 literal strings, each at most 8,192 UTF-16 units.
replacements	Replacement IDs aligned to names. The final full bank must remain distinct, including unchanged IDs.	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.states	State trace or state inventory in the precise initial-state/discovery/bank order described above.
result.alphabet	Renamed alphabet in original bank order.
result.transitions	Rewritten transition records in original transition order.

json

{
  "input": {
    "transitionsJson": "[{\"from\": \"a\", \"symbol\": \"x\", \"to\": \"b\"}, {\"from\": \"b\", \"symbol\": \"x\", \"to\": \"b\"}]",
    "states": [
      "a",
      "b",
      "c"
    ],
    "alphabet": [
      "x"
    ],
    "names": [
      "a"
    ],
    "replacements": [
      "z"
    ]
  },
  "output": {
    "result": {
      "states": [
        "z",
        "b",
        "c"
      ],
      "alphabet": [
        "x"
      ],
      "transitions": [
        {
          "from": "z",
          "symbol": "x",
          "to": "b"
        },
        {
          "from": "b",
          "symbol": "x",
          "to": "b"
        }
      ]
    }
  }
}

Limitations and assumptions

The resulting state bank must remain distinct, including unmapped names. Symbols remain unchanged, and replacement mappings are not applied recursively.
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 State Renaming Transform — tool.io

Similar or alternative tools

DFA Symbol Renaming Transform
Apply an injective alphabet-symbol renaming to a validated deterministic transition table.
DFA Transition Target State Coverage
Audit missing transition targets and sources independently against an explicit declared state bank.