Method sheet

The definitions and every method 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.
The ε-NFA table	state \| ε* \| 0 \| ε* \| 1 \| ε* — closure, symbol, closure again, per symbol	Union the whole closure's rows — reading the symbol from q alone is the usual slip.
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.

Minimising a DFA

Equivalence classes, round by round

0-equivalence	two blocks: {non-accepting} {accepting}	Nothing else is looked at yet — not the arrows, only the rings.
k-equivalence	p, q stay together ⟺ for every symbol a, δ(p, a) and δ(q, a) are in the same block of round k − 1	Compare against the previous round, never the one you are in the middle of writing.
Splitting	blocks only ever split; they never merge back	Two states apart in round k are apart for good.
Stop	when a round equals the one before it	Write the repeated round down — it is the proof you are done.
The minimal DFA	one state per block; read its row from any one member	Cells name blocks, not members: AE, not A.
Start and accepting	start = the block holding q₀; a block accepts when its members did	A block is never half accepting — round 0 saw to that.
Unreachable states	a state no arrow path from q₀ reaches is not part of the machine	Cross it off before round 0.

Moore and Mealy machines

M = (Q, Σ, Δ, δ, λ, q₀) — they print, they do not accept

Δ	the set of output symbols	There is no F. Nothing is accepted or rejected.
λ — Moore	Q → Δ, drawn inside the state: A/0	Output belongs to the state.
λ — Mealy	Q × Σ → Δ, drawn on the arrow: input/output	Output belongs to the transition.
Output length	Moore: n + 1 for an input of n. Mealy: n	The Moore start state prints before anything is read.
Moore → Mealy	each arrow takes the output of the state it enters; Q is unchanged	The state it enters, not the state it leaves.
Mealy → Moore, 1	list the outputs on the arrows into each state	Self-loops are arrows in too.
Mealy → Moore, 2	a state entered with k different outputs becomes k states: B0, B1	Up to \|Q\| × \|Δ\| states. One entered with a single output stays whole.
Mealy → Moore, 3	q —a/x→ p becomes an arrow to the copy of p that prints x	Every copy of q keeps all of q's outgoing arrows.

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.