Finite Automata

Finite Automata (DFA / NFA / ε‑NFA)

Finite automata recognise the regular languages. They have no auxiliary memory — only a current state (DFA) or set of active states (NFA/ε‑NFA).

DFA — Deterministic Finite Automaton

• At most one transition per (state, symbol). A total DFA defines exactly one move for every symbol in every state.
• Exactly one active state at a time.
• Accepts iff the run ends in an accept state after consuming the whole input.

In AutomataLab a partial DFA (a missing (state, symbol)) is allowed — the run simply rejects when it has nowhere to go, exactly as theory dictates. The validator flags missing transitions as a warning and offers a one‑click Complete DFA fix that adds a trap state and the missing edges.

Example — strings over {a,b} ending in a: two states q0 (start) and q1 (accept); a moves toward q1, b toward q0.

NFA — Nondeterministic Finite Automaton

• Many transitions allowed per (state, symbol); the machine explores all of them in parallel.
• The active "state" is really a set of states; the input is accepted if any active state is accepting at the end.
• No ε‑moves — if you need them, use ε‑NFA.

Because branches that reach the same state at the same step are indistinguishable, AutomataLab visualises an NFA run as a trellis (merged paths) rather than an exponentially branching tree — see Simulation.

ε‑NFA — NFA with ε‑moves

• Adds ε‑edges that are taken without consuming input.
• After every move (and on the start state) the engine takes the ε‑closure — the set of all states reachable by ε‑edges.
• Same acceptance rule as the NFA.

Use an ε‑NFA when a construction naturally "guesses" or stitches sub‑machines together (e.g. Thompson's construction from a regex).

Tips

• Switching DFA → NFA → ε‑NFA is always safe (each is a generalisation). Switching the other way may surface a determinism warning if the diagram has multiple moves on a symbol.
• Declare the input alphabet Σ in machine settings to get warnings about edges that read symbols outside it. See Validation & Alphabets.

For the JSON schema and worked examples, see File Format.