The deterministic finite automaton, or DFA, is the simplest model of computation studied in the theory of computation. It is a machine with no external memory: it only knows the state it is in and the symbol it is reading. That very poverty of resources is what makes it useful, because it forces us to ask precisely what can be computed with an amount of memory fixed in advance.
The formal definition
A DFA is a 5-tuple (Q, Σ, δ, q₀, F) where:
- Q is a finite set of states;
- Σ is the alphabet, the finite set of input symbols;
- δ: Q × Σ → Q is the transition function, which maps every (state, symbol) pair to exactly one state;
- q₀ ∈ Q is the start state;
- F ⊆ Q is the set of accepting states.
The word "deterministic" refers to δ: for every state and every symbol there is one and only one possible move. There are no choices, no missing transitions and no moves that happen without reading a symbol.
How a DFA runs
The automaton receives a string w = a₁a₂…aₙ. It starts in q₀, reads a₁ and moves to δ(q₀, a₁), then reads a₂, and so on. When the string ends, it looks at the state it has reached: if that state is in F the string is accepted, otherwise it is rejected. The computation always takes exactly n steps, one per symbol, and it always halts.
The set of all accepted strings is called the language recognized by the automaton, written L(M). Languages recognized by at least one DFA are called regular languages.
A concrete example: binary numbers divisible by 3
Suppose we want to recognize strings over the alphabet {0, 1} that, read as binary numbers, are multiples of 3. The key idea is to keep track of the remainder modulo 3 of the number read so far. If the current remainder is r and we read bit b, the new number equals 2·value + b, so the new remainder is (2r + b) mod 3.
We therefore need three states, one per possible remainder:
| State | Reads 0 | Reads 1 |
|---|---|---|
| r0 (start, accepting) | r0 | r1 |
| r1 | r2 | r0 |
| r2 | r1 | r2 |
Try the string 110, which equals 6. We start in r0; reading 1 takes us to r1; reading 1 brings us back to r0; reading 0 keeps us in r0. The final state is accepting: 6 is divisible by 3. With 101, which equals 5, the path is r0 → r1 → r2 → r2, and the string is rejected.
The DFA does not remember the number, which may be huge, but only a summary of bounded size. Designing an automaton means asking which summary is enough to decide.
How to design a DFA
In my work, when I have to build an automaton by hand, I follow a four-step method:
- Decide what to remember. List the minimum information about the prefix read so far that the final decision needs (a remainder, the last symbol seen, how many times a letter has appeared, up to a cap).
- Give each situation a state. Every relevant combination of that information becomes a state.
- Write every transition. For each state and each symbol, decide where to go. If a situation makes acceptance impossible, add a "sink" state that never leads to acceptance.
- Check edge cases. The empty string, one-symbol strings, strings that almost satisfy the property.
A common mistake is forgetting the sink: in a DFA in the strict sense every state must have a transition for every symbol.
What a DFA cannot do
Because the number of states is finite, a DFA cannot count without bound. The language of strings of the form aⁿbⁿ, that is n letters a followed by the same number of b's, is not regular: to compare the number of b's with the number of a's the automaton would have to remember n, which is unbounded. A rigorous proof comes from the pumping lemma or from the Myhill-Nerode theorem.
This limitation is not a flaw but a guarantee. A DFA uses constant memory and linear time, which is why it underlies lexical analyzers in compilers, communication protocols described as state machines, validators for simple formats and controllers for embedded devices.
Useful properties of regular languages
Several very practical properties follow from DFAs:
- Complement: swapping accepting and non-accepting states gives an automaton that accepts exactly the strings that were rejected before.
- Intersection and union: the product construction simulates two automata in parallel, using pairs of states as states.
- Decidable problems: we can decide whether a DFA accepts at least one string (reachability of an accepting state) and whether two DFAs recognize the same language.
Regular languages are thus a robust class, the first rung towards pushdown automata and Turing machines.
In short
- A DFA is a 5-tuple with finitely many states and exactly one transition for each state-symbol pair.
- It accepts a string if, after reading all of it, it is in an accepting state; the languages recognized this way are the regular ones.
- Designing a DFA means finding the finite summary of the prefix that is enough to decide.
- It cannot count without bound: aⁿbⁿ is not regular.
- Constant memory and linear time make it valuable in compilers, protocols and embedded systems.
