The one question that designs the machine
In guide 2 you pinned down what a DFA IS — the five-tuple, the transition function δ (the Greek letter delta, the rulebook of moves), and the rule that a string is accepted when its run ends in an accept state. That tells you how to read a finished machine. It does not yet tell you how to build one from a plain-English description like 'strings containing 011' or 'an even number of a-s'. This guide is about exactly that leap, and the good news is that almost all of it flows from a single question.
Here is the question, and it is wonderfully concrete: as I scan the input left to right, one symbol at a time, what is the minimum I must remember so far in order to decide later whether to accept? A DFA's only memory is its current state, so every distinct answer to that question — every genuinely different 'situation' the past can leave you in — must become one state. Get the list of situations right and the machine almost draws itself; get it wrong and no amount of arrow-juggling will save you.
Warm-up: parity, and the four-step recipe
Take the language 'strings over {a, b} with an even number of a-s'. Apply the question: to know at the end whether the count of a-s is even, what must I carry along? Not the count itself — that grows without bound — but only its parity: is the count-so-far even or odd? That is one bit, two situations, so two states: E ('a-count is even so far') and O ('a-count is odd so far'). The whole unbounded count collapses into a single bit, and that collapse is the heart of DFA design.
- Name the facts you must track, one state per distinct situation. Here: E and O, the parity of the a-count.
- Choose the start state by asking what is true of the EMPTY input. Zero a-s is an even count, so start in E. (This is also where a DFA's verdict on epsilon, the empty string, is decided.)
- Fill in δ: for each state and symbol, ask which situation you land in next. Reading b never changes the a-count, so it is a self-loop on both states; reading a flips parity, so δ(E,a)=O, δ(E,b)=E, δ(O,a)=E, δ(O,b)=O.
- Mark the accept states — the situations that mean success. 'Even number of a-s' means F = {E}. Done: a correct two-state DFA.
Notice how flexible the last step is. Keep the very same states and δ but flip the accept set to F = {O} and the machine now recognises 'an ODD number of a-s'. The states do the remembering; F only decides which remembered facts you are willing to call a yes. This separation — situations versus which situations win — is worth keeping in mind, because it is exactly what the next guide's product construction exploits to combine conditions.
Counting modulo k: remainders, not totals
Parity is just counting modulo 2, and the same trick scales. Suppose we want binary strings (over {0, 1}, read most-significant bit first) whose numeric value is divisible by 3. The value can be astronomically large, far too big to store. But ask the question again: what is the least I must remember? The answer is the remainder modulo 3 of the value seen so far — one of just three possibilities, 0, 1, or 2. Three situations, three states: r0, r1, r2.
Why does a remainder suffice when the value itself does not? Because of how appending a bit changes the value: reading bit d turns a value v into 2v + d. The remainder of 2v + d modulo 3 depends only on the remainder of v modulo 3 (and on d) — never on the full value. So the transition is pure remainder arithmetic: from remainder r, reading bit d, go to remainder (2r + d) mod 3. That is the whole machine. This is the everyday miracle of modular arithmetic doing the DFA's bookkeeping for it.
Language: binary strings whose value is divisible by 3 (MSB first)
States = remainder mod 3 of the value read so far.
Transition rule: from r, on bit d, go to (2*r + d) mod 3.
| bit 0 | bit 1
----- +------------- +-------------
-> r0*| (2*0+0)=0 r0 | (2*0+1)=1 r1
r1 | (2*1+0)=2 r2 | (2*1+1)=3 r0 (3 mod 3 = 0)
r2 | (2*2+0)=4 r1 | (2*2+1)=5 r2 (4 mod 3 = 1, 5 mod 3 = 2)
-> marks the start state (r0) * marks the accept state (r0)
Trace 110 (= six, divisible by 3): r0 -1-> r1 -1-> r0 -0-> r0 -> accept
Trace 101 (= five): r0 -1-> r1 -0-> r2 -1-> r2 -> rejectThe pattern generalises immediately: for 'divisible by k' use k states r0, ..., r(k-1), start at r0, accept r0, and let reading a symbol update the remainder. This is the cleanest demonstration of why such languages are regular even though they contain infinitely many strings — bounded memory (one of k remainders) is genuinely enough, no matter how long or how large the number gets.
Substrings, overlap, and the pitfall of resetting too far
Now the most practically useful pattern: recognising strings that contain a fixed substring, say 011 somewhere over {0, 1}. The fact to track is 'how much of the pattern 011 have I matched so far, ending right here?'. That gives four situations: matched nothing useful (s0), matched 0 (s1), matched 01 (s2), and found 011 (s3, success). Once you reach s3 the answer is already yes and can never become no, so s3 loops to itself on every symbol — a permanent 'success sink'.
The transitions on a 'wrong' symbol are where almost everyone slips. Sitting in s2 ('I have just seen 01') you read a 0. It is tempting to fall all the way back to s0 — but that is wrong, because the 0 you just read is itself the start of a possible new match. The correct move is to s1 ('matched 0'). You must always ask: after this symbol, what is the LONGEST prefix of 011 that ends right here? Throwing away a partial match that could still be reused is the classic bug, and it is exactly the kind of overlap that string-search algorithms also have to handle.
Flip the requirement to 'does NOT contain 011' and you reuse the very same four-situation tracking — but now s3, the 'found it' state, is the bad outcome. It becomes a non-accepting trap state (also called a dead state): once you have seen 011 the string is doomed, so s3 loops to itself forever and is never accepting, while s0, s1, s2 all accept. The trap is how a DFA records 'a violation has occurred' while still politely reading the rest of the input; it is also what keeps δ total, meaning every (state, symbol) pair has a defined move and the machine never gets stuck.
Combining conditions, and the limit you cannot design around
Real specifications often glue several conditions together: 'an even number of a-s AND the string ends in b', or 'divisible by 3 OR contains 011'. You could try to design such a machine from scratch by listing every combined situation, but there is a mechanical shortcut. Run two finished machines side by side, keeping a state for EACH at the same time; a single state of the combined machine is a pair (one component per condition). This is the product construction, and it is the entire subject of the next guide — so here just notice that 'remember two things at once' is itself just 'remember the pair', which is still a finite set of situations.
Every example so far has worked because the thing to remember was bounded: one parity bit, one of k remainders, one of four match-progress stages, or a pair of these. That is no accident — it is the precise reach of the model, and it has a hard edge. The honest limit is the finite-memory limit: a DFA cannot count without bound. If a language demands tracking an unbounded quantity, no choice of states will work.
The classic example is the language a^n b^n (n copies of a followed by exactly n copies of b, for any n). To check the b-count against the a-count, a machine reading the b-s must recall how many a-s came first — and n can be arbitrarily large. With any fixed number of states, two different a-counts must eventually land in the same state (this is the pigeonhole principle in disguise), after which the machine behaves identically on both and is forced to misjudge one. So no DFA recognises a^n b^n; it is not regular. Crucially, 'unbounded' is the operative word: a DFA CAN check 'at most 1000 a-s' (just use enough states) — it fails only when the bound itself is allowed to be any number. That boundary, and the tool that escapes it (a stack), is what later rungs build on.