Validation and Alphabets

Validation & Alphabets

AutomataLab validates your machine continuously and surfaces issues in the Validation tab. Items are click‑to‑locate — selecting one jumps to and highlights the offending state or edge on the canvas.

Errors vs. warnings

• Errors block a meaningful run (e.g. no start state, a transition referencing a missing state, or a state that is both accept and reject).
• Warnings are advisory and never block a run. They flag things that are legal but probably unintended.

Common checks

Check	Severity	Notes
No start state / more than one	Error	Exactly one start state is required.
Transition endpoint missing	Error	from/to must reference existing states.
Accept and reject on one state	Error	TM/LBA only; mutually exclusive.
Unreachable state	Warning	No path from the start state.
Nondeterminism in a deterministic type	Warning/Error	DFA/DPDA/TM/LBA expect ≤ 1 applicable move; the check is on (state, symbol) for DFA, configuration for DPDA, and the (state, read) / read‑tuple for TM.
Partial DFA (missing (state, symbol))	Warning	A missing move simply rejects — see below.
Symbol outside a declared alphabet	Warning	See Declared alphabets.

Partial DFA & the "Complete DFA" fix

A DFA with a missing (state, symbol) transition is not an error in AutomataLab — per theory, the run just rejects when it has nowhere to go. The validator marks it as a warning and offers a one‑click Complete DFA quick‑fix that adds a single trap (dead) state and routes every missing (state, symbol) to it, turning a partial DFA into a total one without changing the language.

Declared alphabets — Σ and Γ

Declaring alphabets is optional and declarative: it powers helpful warnings but the engine never enforces it, so machines stay runnable.

• Σ — input alphabet (alphabet): the symbols your machine reads. Edges that read a symbol outside Σ are flagged.
• Γ — stack alphabet (STACK (Γ), DPDA/NPDA): the symbols allowed on the stack. A pop/push symbol outside Γ is flagged.
• Γ — tape alphabet (TAPE (Γ), TM/LBA): the symbols allowed on the tape; should include the blank and satisfy Σ ⊆ Γ. A written symbol outside Γ — or the blank appearing in Σ — is flagged.

Set these in the toolbar's machine settings. Leaving an alphabet empty simply skips its checks. The declared alphabets are saved with the machine (see File Format) and are fully backward compatible — older files just omit them.