Machine Types

Machine Types

AutomataLab implements seven machine types spanning the Chomsky hierarchy of formal languages. Pick the type in the toolbar; the canvas, transition editor, validator, and panels all adapt.

Type	Name	Recognises	Memory	Determinism
DFA	Deterministic Finite Automaton	Regular languages	none	≤ 1 move per (state, symbol)
NFA	Nondeterministic Finite Automaton	Regular languages	none	many moves per (state, symbol)
ε‑NFA	NFA with ε‑moves	Regular languages	none	+ ε‑closure each step
DPDA	Deterministic Pushdown Automaton	a subset of CFLs	stack	≤ 1 applicable move per config
NPDA	Nondeterministic Pushdown Automaton	Context‑free languages	stack	branches explored in parallel
TM	Turing Machine	Recursively enumerable	two‑way infinite tape(s)	≤ 1 move per (state, read)
LBA	Linear‑Bounded Automaton	Context‑sensitive	tape bounded to the input	≤ 1 move per (state, read)

The hierarchy nests: every DFA is an NFA, every NFA is an ε‑NFA, and a finite automaton is a PDA that ignores its stack, which in turn is a TM that never moves left or writes. AutomataLab lets you switch a machine's type — useful for showing that "every DFA is also an NFA," though moving down the hierarchy (e.g. NPDA → DFA) may flag determinism/feature warnings.

Acceptance, at a glance

• DFA / NFA / ε‑NFA — accept iff, after the entire input is consumed, the machine is in (DFA) or its active set contains (NFA/ε‑NFA) an accept state.
• DPDA / NPDA — accept by final state: input fully consumed and a current branch is in an accept state. The stack need not be empty (emulate empty‑stack acceptance with a bottom marker like Z).
• TM / LBA — accept by halting in an accept state (the input need not be "consumed"; the head can be anywhere). A run rejects on an explicit reject state or when no transition applies from a non‑accept state. It halts as stuck if it exceeds the step limit (loop guard); an LBA also rejects if the head crosses a tape boundary.

Common rules

• Exactly one start state. Zero or more accept states.
• Every transition references existing states.
• ε / empty is written ε on finite‑automaton edges and as an empty field on PDA/TM operations. Accepted spellings: "", ε, eps, λ, lambda.

Learn each family

• Finite Automata — DFA, NFA, ε‑NFA.
• Pushdown Automata — DPDA, NPDA, and the stack convention.
• Turing Machines & LBA — the tape, multi‑tape TMs, reject states, and the bounded LBA head.

For the exact JSON each type uses, see File Format.