Introduction
The simplest useful machine has no memory except the state it is in. A deterministic finite automaton (DFA) reads its input one symbol at a time, changes state after each symbol, and at the end answers yes or no. Despite its simplicity it powers lexers, protocol checkers, vending machines and the regular-expression engines behind every text editor.
"Deterministic" means there is never a choice: in each state, each symbol leads to exactly one next state. "Finite" means the number of states is fixed in advance, no matter how long the input is.
How it works
A DFA has five parts, written M = (Q, Σ, δ, q0, F):
- Q, a finite set of states;
- Σ, the input alphabet;
- δ, the transition function: δ(q, a) is the state reached from q on symbol a;
- q0, the start state;
- F, the set of accepting (final) states.
To run M on a string, start in q0 and, for each symbol, move to δ(current, symbol). After the last symbol, M accepts if the current state is in F and rejects otherwise. The language L(M) is the set of strings M accepts.
A transition table lists δ compactly, with one row per state and one column per symbol. Here is the DFA that accepts strings with an even number of a's; state E means "even so far" and O means "odd so far":
delta = {("E", "a"): "O", ("E", "b"): "E", ("O", "a"): "E", ("O", "b"): "O"}
print("state | a | b")
for state in ["E", "O"]:
print(f" {state} | {delta[(state, 'a')]} | {delta[(state, 'b')]}")The key idea is that a state is a summary of everything that matters about the input read so far. To decide divisibility by 3, the DFA does not need the whole number; it only needs the remainder so far, so three states are enough. Reading bit b turns remainder r into (2r + b) mod 3, because appending a bit doubles the value and adds b.
In Python, δ is a dictionary keyed by (state, symbol) pairs, and a run is a loop.
Syntax
delta = {("q0", "a"): "q1", ("q0", "b"): "q0", ...} # δ
start, accept = "q0", {"q1"} # q0 and F
state = start
for symbol in word:
state = delta[(state, symbol)] # one move per symbol
accepted = state in accept
Example
delta = {
("r0", "0"): "r0", ("r0", "1"): "r1",
("r1", "0"): "r2", ("r1", "1"): "r0",
("r2", "0"): "r1", ("r2", "1"): "r2",
}
start, accept = "r0", {"r0"}
def run(word):
state = start
path = [state]
for symbol in word:
state = delta[(state, symbol)]
path.append(state)
return state in accept, path
for word in ["110", "111", "1001", "0"]:
ok, path = run(word)
print(word, "=", int(word, 2), "->", " ".join(path), "accept" if ok else "reject")Line by line
- The states r0, r1 and r2 stand for the remainders 0, 1 and 2 of the value read so far.
- Each entry of
deltafollows the rule new remainder = (2 × remainder + bit) mod 3; for example from r1 on 1: (2 + 1) mod 3 = 0, so r0. runstarts in r0, applies δ once per symbol and records the path, the states visited.- The word is accepted when the run ends in r0, that is, when the value is divisible by 3. 110 is 6 and 1001 is 9, so both are accepted; 111 is 7, so it is rejected.
Expected result
110 = 6 -> r0 r1 r0 r0 accept
111 = 7 -> r0 r1 r0 r1 reject
1001 = 9 -> r0 r1 r2 r1 r0 accept
0 = 0 -> r0 r0 accept
In the real world
The lexer of every compiler is a DFA that splits source code into tokens. TCP's connection states, traffic lights, elevator controllers and many games' AI behaviour are designed as finite state machines. Because a DFA reads each symbol once and does constant work per symbol, it runs in linear time with no extra memory, which is why it suits hardware and very large inputs.
Common mistakes
- Leaving a transition out: a DFA must have exactly one move for every state and every symbol; use a "dead" state for inputs that can never be accepted.
- Accepting by "reaching" a state in the middle: only the state at the very end of the input counts.
- Forgetting the empty string: ε is accepted exactly when the start state is accepting.
- Giving the DFA memory it does not have, such as a counter that can grow without limit.
Best practices
- Name each state after what it remembers, such as "even" or "remainder 2".
- Write the table first, then check every row has one entry per symbol.
- Test the shortest strings first: ε, then each single symbol.
Summary
A DFA is (Q, Σ, δ, q0, F). It starts in q0, makes one move per symbol, and accepts if it ends in F. Its states are a finite summary of the input so far. In Python, δ is a dictionary and a run is a loop, so any DFA can be simulated in a few lines.
Quick check
Key takeaways
- A DFA is (Q, Σ, δ, q0, F): states, alphabet, transitions, start, accepting states.
- It reads each symbol once, left to right, and never looks back.
- The language of a DFA is every string whose run ends in an accepting state.
Practice problems for this lesson
My notes
Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.