Method sheet

The definitions and the four conversions on one page, written as the steps you actually perform. The right-hand column is the mistake that particular line invites.

The 5-tuple

M = (Q, Σ, δ, q₀, F)

Q	the set of all states	Every circle in the diagram, including any dead state.
Σ	the set of input symbols	ε is never in Σ — it is not an input.
δ — DFA	Q × Σ → Q	Exactly one state per cell. Never a set, never empty.
δ — NFA	Q × Σ → 2^Q	A cell may hold two states, or Φ.
q₀	the start state — one only	The loose arrow with no source.
F	the set of accepting states, F ⊆ Q	Double ring. F may be empty; it is still a set.
Reading a diagram	one row per state, one column per symbol	An arrow labelled 0,1 is two table entries.

The three machines

Every DFA is an NFA; not every NFA is a DFA

DFA	deterministic, complete, no ε	Complete matters: a missing arrow means it is not yet a DFA.
NFA	may branch, may have empty cells, no ε	No dead state is required — Φ is a legal cell.
ε-NFA	NFA plus transitions taken without reading input	ε moves happen spontaneously, before and after every symbol.
Power	DFA ≡ NFA ≡ ε-NFA — all accept exactly the regular languages	Nondeterminism buys brevity, not power.
Acceptance	accept if ANY sequence of choices ends in F	One accepting path is enough; the rest may die.

NFA → DFA

Subset construction

1. Start	the DFA start state is {q₀}	A set, even when it has one member.
2. Each cell	δ′(S, a) = ⋃ over q ∈ S of δ(q, a)	Union the NFA rows — do not read them one at a time.
3. New sets	every set that appears becomes a new row	Stop only when no new set appears.
4. Dead state	the empty set is a state; it self-loops on every symbol	Give it the next unused label and draw its loop.
5. Accepting	S accepts ⟺ S ∩ F ≠ ∅	One accepting member is enough.
Size	at most 2^\|Q\| states, usually far fewer	Only the reachable subsets are drawn.

ε-NFA → NFA

ε-Closure and ε*·a·ε*

ε-Closure(q)	every state reachable from q on ε alone	q is always in its own closure. Follow ε chains all the way.
New transition	δ′(q, a) = ε-Closure( δ( ε-Closure(q), a ) )	Closure on both sides — before the symbol and after it.
New accepting states	q ∈ F′ ⟺ ε-Closure(q) ∩ F ≠ ∅	This is where marks go. The start state often becomes accepting.
States and start	unchanged	Only δ and F change; Q and q₀ stay as they were.

ε-NFA → DFA

Do it in two moves, not one

1.	ε-NFA → NFA by closures, as above	Finish F′ before going on — the DFA inherits it.
2.	NFA → DFA by subset construction	Subsets of the NFA's states, using the new δ′.
Shortcut	or subset-construct directly with ε-Closure applied at every step	Same answer, more places to slip. Two clean tables beat one clever one.

Designing a machine

From a language description

starts with p	spell p out, then accept everything	Any mismatch goes to a dead state and stays there.
ends with p	NFA: loop Σ, then spell p. DFA: track how much of p the tail matches	After a mismatch you often land part-way into p, not back at the start.
contains p	spell p; the accepting state loops on all of Σ	Once seen, it cannot be unseen — the final state is absorbing.
length exactly k	k + 1 states in a chain, plus a dead state	Symbol k+1 must go somewhere non-accepting.
count of a ≡ r (mod m)	m states in a ring; other symbols self-loop	Only the counted symbol advances the ring.
every x followed by y	ok / owing / dead — the owing state is not accepting	A string that ends while still owing must be rejected.