A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
A deterministic finite automaton (DFA) is a 5-tuple (Q, Σ, δ, q₀, F) consisting of a finite set of states, an input alphabet, a transition function that maps each state-symbol pair to exactly one next state, a start state, and a set of accept states. A DFA accepts a string if the computation starting from q₀ ends in an accept state after consuming all input. DFAs are the simplest model of computation and recognize exactly the class of regular languages. Unlike more powerful models, DFAs have no memory beyond which state they currently occupy.
Draw state diagrams by hand for simple languages (e.g., 'all strings ending in 01') before attempting formal tuple definitions. Trace specific strings step-by-step through the transition function to build intuition. Then try to construct DFAs for slightly harder languages (divisibility by 3 in binary, balanced pairs of characters) to sharpen pattern recognition.
You already know finite-state machines from your prerequisites — machines with states, transitions, and the ability to accept or reject inputs. A DFA is the precise formalization of that idea. The 5-tuple (Q, Σ, δ, q₀, F) gives each component a name: Q is the finite set of states, Σ is the input alphabet, δ is the transition function, q₀ is the start state, and F ⊆ Q is the set of accept states. The entire machine is pinned down once you specify these five components.
The transition function δ is the heart of the definition. It takes a state and a single input symbol and returns exactly one new state: δ(q, a) = q'. "Exactly one" is the "deterministic" in DFA — there is never a choice. To process a string, you start in q₀ and apply δ one symbol at a time. After consuming the last symbol, check whether you're in an accept state. If yes, the DFA accepts; if no, it rejects. The machine is always in exactly one state, and the path through states is completely determined by the input.
A common misconception is that a DFA can get stuck — that is, reach a state with no valid transition. A *complete* DFA never gets stuck because δ is defined for *every* (state, symbol) pair. Whenever a transition would otherwise be undefined, you add a dead state (also called a trap state): transitions to the dead state loop back to itself and it is not an accept state. The dead state simply absorbs all inputs that lead to rejection. This keeps δ a total function.
The states in a DFA are your only memory. The machine remembers nothing about the input except which state it's currently in. This is a profound limitation: a DFA with k states can "distinguish" at most k different situations. This is why DFAs recognize exactly the regular languages — languages like "strings ending in 01" or "binary numbers divisible by 3" — but cannot recognize languages that require counting to an arbitrary depth, like balanced parentheses or equal numbers of a's and b's. For those, you need a model with more memory (a pushdown automaton or Turing machine).
When building DFAs, draw state diagrams before writing formal tuples. Ask yourself: what does the machine need to *remember* to decide acceptance? Each distinct "memory configuration" becomes a state. For the language "all strings over {0,1} that end in 01," the machine needs to remember the last two symbols seen — yielding states for "last seen nothing special," "last seen a 0," and "last seen 01." This state-based thinking directly generalizes to the more powerful automata you will study next.