A machine whose whole memory is one state
From the earlier rungs you already know that a regular language is the first family on the Chomsky hierarchy, the simplest patterns of strings over an alphabet Σ. Now we meet the machine that recognizes exactly those patterns. Picture a subway turnstile: right now it is locked, you push a coin in and it becomes unlocked, you walk through and it locks again. It does not remember how many people passed yesterday or how many coins it has ever swallowed — at every instant, everything it knows is one word, locked or unlocked. That single word is its state, and a device whose whole memory is one state chosen from a fixed finite list is a finite-state machine.
A finite-state machine reads its input one symbol at a time, strictly left to right, and after each symbol it sits in exactly one state. The only thing carried from one symbol to the next is which state you are in — no scratch pad, no counter, no storage on the side. A rule says, for the current state and the symbol just read, which state to move to. A traffic light cycling green to yellow to red, and a vending machine tracking how much money is in so far, are everyday finite-state machines.
Making it precise: the DFA five-tuple
The specific finite-state machine of this rung is the deterministic finite automaton, or DFA. The word deterministic is a promise: there is never any choice. Given where you are and what you just read, the next state is completely fixed — run the same machine on the same input a thousand times and you trace the same path every time. To pin a DFA down without drawing a picture, we package it as a five-tuple M = (Q, Σ, δ, q0, F), the full recipe card for the machine.
Reading the five ingredients in order: Q is the finite set of states (the circles in a picture). Σ (capital sigma) is the input alphabet, the finite set of symbols the machine may read. δ (the Greek letter delta) is the transition function: it takes one state and one symbol and returns exactly one next state, written delta(q, a) = p, meaning 'from state q, reading symbol a, go to state p'. q0 is the start state, where every run begins. F (a subset of Q) is the set of accept states, drawn as double circles, that say 'if you finish here, the answer is yes'. That is the entire machine — nothing left to guess.
Two quiet conditions hide in that signature, and together they spell out the 'D' in DFA. Deterministic: delta returns a single state, never a set and never a choice. Total: delta is defined for every state and every symbol, so the machine never gets stuck not knowing what to do. In a correct DFA, every state has exactly one outgoing arrow per alphabet symbol — every cell of its table is filled with exactly one entry.
Two ways to draw it, one way to run it
The same DFA can be shown two ways. A state diagram is the picture: each state a circle, each transition a labelled arrow, the start state with a stray arrow pointing in from nowhere, each accept state a double circle. A transition table is the spreadsheet: one row per state, one column per symbol, and the cell where row q meets column a holds delta(q, a). They are two views of the very same object — every arrow labelled a from q to p is exactly the equation delta(q, a) = p.
Running a string is a single, tame walk. Put your finger on the start circle. For each input symbol, follow the one arrow leaving your current circle whose label is that symbol (there is exactly one, because delta is total and deterministic). When the input runs out, look at where your finger rests: a double circle means accept, otherwise reject. This is a run, and it has two lovely properties — it is unique (no branching to explore) and it is exactly as long as the input (n symbols take n steps, using only the memory of one state). Below is a tiny machine that accepts binary strings ending in 1, run on the input 1101.
DFA "ends in 1" alphabet {0,1} start: A accept: { B }
transition table state diagram (-> marks start, (( )) = accept)
state | 0 | 1 0 1
----- | - | - +------+ -----1---> (( B ))
-> A | A | B ->| A |<----0------ || B ||
B | A | B +------+
run on 1101 (one path, length 4):
A --1--> B --1--> B --0--> A --1--> B end state B is in F => ACCEPT
run on 1100:
A --1--> B --1--> B --0--> A --0--> A end state A not in F => REJECTTwo honest reminders about acceptance. First, only the FINAL state matters: passing through an accept state partway means nothing, what counts is where you stand when the input is exhausted. Second, a DFA never crashes — because delta is total, every string gets a clean verdict, and rejection is a deliberate, well-defined outcome, not an error.
Designing a DFA: pick the right facts to remember
Here is the whole art of DFA design: each state should stand for exactly one fact (or combination of facts) about the input read so far — and the set of states should capture every fact you will ever need, no more. Then you accept a string precisely when the fact you care about is true at the end. Let us design a DFA for the language 'strings with an even number of a-s' over Σ = {a, b}. The only fact that matters is the parity of the a-count: is it even or odd? That is two situations, so two states, named Even and Odd.
- Pick the start state. Before any symbol is read, zero a-s have been seen, and zero is even — so start in Even. (Getting this base case right is as important as the transitions; the empty string epsilon must land where it belongs.)
- Write the transitions. Reading b never changes the a-count, so b is a self-loop on both states: delta(Even, b) = Even and delta(Odd, b) = Odd. Reading a flips the parity: delta(Even, a) = Odd and delta(Odd, a) = Even.
- Choose the accept states. We want an even count at the end, so F = { Even }. Since the start state Even is also accepting, the machine correctly accepts epsilon (zero a-s is even). Done: four transitions fully specify a two-state DFA.
The same recipe scales up. For 'binary value divisible by 3', remember the remainder of the value-so-far modulo 3 — three states r0, r1, r2, accept r0; that is counting modulo k with exactly k states. For 'contains the substring ab', let the states track how much of the pattern you have matched so far (seen nothing, just saw an a, saw ab) and make the last one a trap you never leave. Notice the trick: in every case you are tracking a small, bounded summary of the past, never the raw input itself.
Dead states, the language of a DFA, and the one hard limit
Sometimes a string goes wrong in a way it can never recover from — say you are matching a fixed pattern and read a symbol that ruins it forever. To keep delta total, you send such inputs to a trap state (also called a dead state): a non-accepting state whose every arrow loops right back to itself. Once you fall in, you never climb out, and the string is doomed to reject. A trap state is not a bug; it is the honest, total way to say 'this input has already failed', and it keeps every cell of the table filled.
Running a DFA decides one string at a time. Collect ALL the strings a machine M accepts into one set and you get the language of the DFA, written L(M) — the set of every string whose unique run ends inside F. A language is called regular exactly when SOME DFA recognizes it. This is the precise meaning of the first rung of the Chomsky hierarchy, and it is the lens to keep: every later machine in this subject is really a different answer to 'which family of languages can it recognize?'.
And now the deepest single lesson of this rung, the finite-memory limit. Because Q is finite, a DFA can distinguish only finitely many situations. It can remember the last symbol, or a parity, or a remainder modulo k, or how far along a fixed pattern it is — but it cannot remember an UNBOUNDED running count. Try to build a DFA for a^n b^n (n a-s then exactly n b-s, for any n): to check the b-s match, you would need to recall how many a-s came first, and that number has no ceiling. With only k states, two different a-counts must eventually land in the same state, and from there the machine can no longer tell them apart. A DFA simply cannot count without bound.
This is not a failure of cleverness; it is a provable wall, and the later pumping lemma (the pigeonhole principle in disguise) will let us prove it rigorously. The wall is also the reason the climb continues: to count without bound we will hand the machine a stack of plates in the pushdown automaton, the next big step up the hierarchy. For now, you can read a DFA, run it, design it for substrings, parity, and counting modulo k, and you can name its one true limit.