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.

QStates

A finite set of states the machine can be in. Example: {q0, q1, q2}

ΣAlphabet

The finite set of input symbols. Example: {0, 1} or {a, b, c}

δTransition fn.

δ: Q × Σ → Q maps (state, symbol) → next state. Must be total.

q₀Start state

The state where computation begins. Exactly one start state.

FAccept states

Subset of Q. If computation ends here, the string is accepted.

Example DFA accepting strings ending in '1' over Σ={0,1}
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  ✗ REJECT

In 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.

Ready to try it yourself?

Open the interactive DFA Minimizer, build an automaton, and run the table-filling algorithm with live step-by-step visualization.