From a feeling to five pieces
In the previous guide you met the finite-state machine as a feeling: a turnstile, a light switch, a vending machine that remembers nothing about its history except the single state it is currently sitting in. That intuition is exactly right, but a feeling cannot be proven about, or fed to a computer, or argued over in a textbook. So this guide does the grown-up thing — it turns that turnstile into a precise mathematical object called a deterministic finite automaton, or DFA for short. Nothing new happens conceptually; we are just writing the turnstile down so carefully that there is no room left for hand-waving.
The whole machine bundles into exactly five things, traditionally written as a 5-tuple (Q, Σ, δ, q0, F). Do not let the Greek scare you — each slot is something you already understand from the turnstile. Q is the finite set of states (the moods the machine can be in). Σ (Sigma) is the input alphabet (the symbols it reads, the same alphabets from the foundations rung). δ (delta) is the transition function (the wiring that says where each push of a symbol sends you). q0 is the start state (the mood you boot up in). And F is the set of accept states (the moods that mean 'yes'). That is the entire machine — five labels on a box.
The transition function δ, drawn two ways
The heart of the machine is the transition function δ. We write a single step as delta(q, a) = p, read 'from state q, reading symbol a, go to state p.' If Q has 3 states and Σ has 2 symbols, then δ must answer 3 times 2 = 6 such questions — one for every state-and-symbol pair — and it must answer every one of them. There are two standard ways to lay these answers out, and they say exactly the same thing: a state diagram (a picture) and a transition table (a grid).
A state diagram draws each state as a circle and each transition as a labelled arrow between circles. Three small conventions carry all the extra information: the start state q0 has a little arrow coming in from nowhere; an accept state in F is drawn as a double circle; and the label on an arrow is the symbol that triggers it. To picture our running example, take the language 'an even number of a's' over Σ = {a, b}. Two states are enough: q_even (we have seen an even count of a's so far) and q_odd. Reading a flips you between them; reading b leaves you put. Start in q_even, and make q_even the only accept state.
Language: strings over {a,b} with an EVEN number of a's.
State diagram (in words):
->( q_even )) <-- start AND accept (double circle)
q_even --a--> q_odd q_even --b--> q_even
q_odd --a--> q_even q_odd --b--> q_odd
Transition table (the SAME machine):
| a | b
---------+--------+--------
->* q_even| q_odd | q_even -> = start
q_odd | q_even | q_odd * = accept state
Trace on input a b a :
q_even --a--> q_odd --b--> q_odd --a--> q_even (in F) => ACCEPT
Trace on input a b b :
q_even --a--> q_odd --b--> q_odd --b--> q_odd (not F) => REJECTThe transition table above is just the diagram with the arrows rearranged into a grid: one row per state, one column per symbol, and the cell holds the destination. Notice the table can never have a blank cell and can never list two states in one cell — if it did, δ would not be a function, and the machine would not be a DFA. The picture is friendlier for humans; the table is friendlier for a computer that has to store the machine. They are interchangeable, and good practice is to sketch one and check it against the other.
Running the machine: from one step to a whole string
A single δ step reads one symbol. To process a whole string you simply do it again and again, feeding the symbols left to right and never looking back. This is the run of the DFA on the input, and it is utterly mechanical — there are no decisions to make, because δ already decides everything. Start in q0, read the first symbol, follow the one arrow, read the next symbol from the state you landed in, follow that arrow, and keep going until the string is exhausted.
- Set the current state to the start state q0, and put a reading finger at the leftmost symbol of the input.
- Read the symbol under your finger, call it a; replace the current state with delta(current, a). Exactly one arrow always applies — that is determinism doing its job.
- Slide your finger one symbol to the right and repeat the previous step.
- When the finger runs off the right end (the string is finished), stop and look at the state you are now sitting in.
- If that final state is an accept state (it is in F), the machine accepts the string; otherwise it rejects. The yes/no comes only from where you ended, never from the path you took.
The empty string ε deserves one careful word. Running ε means you read no symbols at all, so you never move — the run begins and ends in q0. Therefore a DFA accepts ε if and only if its start state q0 happens to also be an accept state. In our even-a's machine, q0 = q_even is an accept state, so ε is accepted: zero a's is an even number of a's, which is exactly right. Theorists capture 'where the run ends after reading a whole string w' with the extended transition function, usually written with a hat, but you have already been computing it by hand in the steps above.
Dead ends: trap states and total wiring
Because δ must answer for every state-and-symbol pair, a DFA is totally wired — there is never a missing arrow to fall through. Beginners often draw a half-finished diagram where some symbol simply has no arrow out of a state, and then wonder what happens when that symbol arrives. In a true DFA that cannot happen; the wiring is total, a property sometimes spelled out as the total transition function. When the language you want truly forbids some symbol once a bad thing has been seen, you do not delete an arrow — you route it into a special state called a trap state (also called a dead state).
A trap state is a roach motel: once you check in, you never check out. Every symbol from the trap loops straight back to the trap, and the trap is not an accept state. So the instant the input does something fatal, you fall into the trap and are doomed to reject no matter what follows. Imagine a machine for 'strings that do not contain the substring aa.' The moment you read a second a in a row, no future symbol can ever fix it — so you send that transition to a trap and let it absorb the rest of the input. The trap is how a DFA says 'I have already decided no, but I am contractually obliged to keep reading.'
Acceptance and the language of a DFA
We can now say crisply what it means for a DFA to do its job. A DFA accepts a string w when the run on w ends in an accept state, and rejects otherwise — that single rule is acceptance. Now gather up every string the machine accepts into one set. That set is the language of the DFA, written L(M) for a machine M. It is a subset of Σ* — exactly the kind of formal language carved out of the universe of strings back in the foundations rung. The machine and its language are two views of one thing: build the machine, and you have implicitly described its language; describe the language, and you are implicitly asking for a machine.
Any language that some DFA accepts earns the most important name in this whole rung: it is called a regular language. This is the entire point of building DFAs — they are not the goal, they are the definition of a class of languages. And one warning to carry forward, because it trips up nearly everyone: regular does not mean finite. Our even-a's language contains infinitely many strings (b, abab, aa, bbaa, and so on without end), yet it is regular because a tiny 2-state machine recognizes it. Size and regularity are different axes entirely; a language can be infinite and still be among the simplest things a machine can recognize.
Designing little machines — and one wall
The skill the next guide drills is design: starting from a description in English and ending with a DFA. The secret is to ask, 'What is the least I must remember to decide the answer?' — and make exactly that the states. For 'even number of a's' the only thing worth remembering is parity, so two states suffice. For 'the number of a's is a multiple of 3' you remember the count modulo 3, giving three states q0, q1, q2 in a little loop. For 'contains the substring ab' you remember how much of the pattern ab you have matched so far. Each design is just a careful answer to that one question about memory.
Two designs often want to hold at once — say, 'an even number of a's AND a number of b's that is a multiple of 3.' You do not have to be clever: run both machines side by side, letting each state remember a pair (parity of a's, count of b's mod 3). That gives 2 times 3 = 6 combined states, and it always works. This trick has a name, the product construction, and it is the whole story of guide 4 in this rung — for now just notice that two finite memories combine into one finite memory, so the result is still a DFA.
But there is a wall, and it is the most honest thing this rung will teach you: a DFA cannot count without bound. Its memory is the finite set Q, fixed before it ever sees an input. Ask it to recognize a^n b^n — n copies of a followed by exactly n copies of b, for every n — and it must somehow remember how many a's went by, where n could be a million or a billion. With only, say, 100 states, two different a-counts must eventually land in the same state (this is the pigeonhole idea you will sharpen into the pumping lemma), after which the machine can no longer tell those counts apart. This finite-memory limit is not a failure of cleverness; no DFA whatsoever can do it. That single wall is the reason the ladder continues — to a machine that adds a stack and can finally count. The last guide of this rung is devoted entirely to staring honestly at this wall.