DFA Theory & Minimization
A complete guide to Deterministic Finite Automata — from basic definitions to the Myhill–Nerode theorem. Click any section below to expand it, then open the app to practice.
A Deterministic Finite Automaton is a mathematical model of computation. It reads an input string one character at a time and transitions between a finite set of states based on defined rules. At the end, it either accepts or rejects the string.
A DFA is formally defined as a 5-tuple: M = (Q, Σ, δ, q₀, F) where Q is the set of states, Σ is the input alphabet, δ is the transition function, q₀ is the start state, and F ⊆ Q is the set of accepting states.
A finite set of states the machine can be in. Example: {q0, q1, q2}
The finite set of input symbols. Example: {0, 1} or {a, b, c}
δ: Q × Σ → Q maps (state, symbol) → next state. Must be total.
The state where computation begins. Exactly one start state.
Subset of Q. If computation ends here, the string is accepted.
States: Q = {A, B}
Alphabet: Σ = {0, 1}
Start: q₀ = A
Accept: F = {B}
Transitions:
δ(A, 0) = A (stay, still no trailing 1)
δ(A, 1) = B (found a 1, now accepting)
δ(B, 0) = A (tail broken, go back)
δ(B, 1) = B (stay in accepting)
Test "101": A →¹ B →⁰ A →¹ B ✓ ACCEPT
Test "110": A →¹ B →¹ B →⁰ A ✗ REJECTIn the DFA Minimizer app, double-click a state to toggle it as a final state. States are automatically labeled and you can drag them anywhere on the canvas.