Deterministic finite automata
Deterministic finite automata (DFA) are simple state machines that recognise regular languages; they are used in lexical analysis, pattern matching and protocol design.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Deterministic finite automata (DFA) are simple machines that decide if an input string belongs to a fixed set of strings called a regular language. Engineers use DFAs in lexical analysers (tokenisers), simple protocol validators, hardware pattern detectors and anywhere a fixed pattern must be recognised with minimal memory.
Key ideas
Start from basic terms and build up the machine formally. I define each term before using it.
- Alphabet (Σ): a finite non-empty set of symbols. Example: Σ = {0,1}.
- String (word): a finite sequence of symbols from Σ. The empty string is denoted ε.
- Σ*: the set of all finite strings over Σ (including ε).
- Language: any subset of Σ*, i.e. a set of strings.
- State: a configuration of the automaton; usually drawn as a circle and given a name like q0, q1.
- Start state (q0): the state where the automaton begins before reading any input.
- Accepting (final) state: a state in which, if the input ends there, the automaton accepts the string. We denote the set of accepting states by F.
- Transition function (δ): for a deterministic automaton, a function that tells which single next state is reached from a given state on a given input symbol.
Formal definition (exact statement universities expect):
- A deterministic finite automaton (DFA) is a 5-tuple M = (Q, Σ, δ, q0, F) where
- Q is a finite set of states.
- Σ is a finite input alphabet.
- δ: Q × Σ → Q is the (total) transition function.
- q0 ∈ Q is the start state.
- F ⊆ Q is the set of accepting (final) states.
Assumption: By definition above δ is total (defined for every pair (q, a)); if a proposed automaton has missing transitions, you must add a dead (sink) state to make δ total before applying some theorems (e.g. complement construction).
Extended transition function and acceptance:
Define the extended transition function δ*: Q × Σ* → Q by:
- δ*(q, ε) = q.
- For x ∈ Σ*, a ∈ Σ: δ*(q, xa) = δ(δ*(q, x), a).
A string w ∈ Σ* is accepted by M if δ*(q0, w) ∈ F.
The language accepted (or recognised) by M is L(M) = { w ∈ Σ* | δ*(q0, w) ∈ F }.
Basic facts and standard theorems (exact statements):
- Every DFA recognises a regular language. (Definition: regular languages are those recognised by some finite automaton or described by a regular expression. The equivalences with NFA, regular expressions and regular grammars — i.e., right-linear (equivalently, left-linear) grammars — are other topics in the course.)
- Determinism vs nondeterminism: In a DFA, δ maps to exactly one state. In an NFA (nondeterministic finite automaton) δ may map to a set of states; conversion from NFA to DFA is done by the subset construction (covered in the separate topic "Nondeterministic finite automata and NFA to DFA conversion").
- Subset-construction size bound: Given an NFA with n states, the equivalent DFA produced by the subset construction can have at most 2^n states. (Assumes standard subset construction; see that topic for algorithm and proof sketch.)
- Closure properties and product construction for DFA (same alphabet Σ required):
- Intersection: if M1 = (Q1, Σ, δ1, q01, F1) and M2 = (Q2, Σ, δ2, q02, F2), then M∩ = (Q1×Q2, Σ, δ×, (q01,q02), F1×F2), where δ×((p,r), a) = (δ1(p,a), δ2(r,a)).
- Union: M∪ = (Q1×Q2, Σ, δ×, (q01,q02), (F1×Q2) ∪ (Q1×F2)).
- Difference: M\ = (Q1×Q2, Σ, δ×, (q01,q02), F1×(Q2 \ F2)).
- Complement: as below; requires a complete DFA (total δ). If alphabets differ, first complete each DFA on the common Σ by adding a dead state.
Proofs universities commonly ask for (include step-by-step):
- Proof by induction that δ*(q, xy) = δ*(δ*(q, x), y) for all q ∈ Q and x,y ∈ Σ*.
- Base: If y = ε, δ*(q, xε) = δ*(q, x) and δ*(δ*(q,x), ε) = δ*(q,x); equal.
- Inductive step: assume true for y of length k. Let y = zb with b ∈ Σ and |y| = k+1. Then δ*(q, xzb) = δ(δ*(q, xz), b). By IH δ*(q, xz) = δ*(δ*(q,x), z). So δ(δ*(q, xz), b) = δ(δ*(δ*(q,x), z), b) = δ*(δ*(q,x), zb). QED.
Diagram conventions (what to draw and label):
- Draw a circle for each state with its name inside (q0, q1 ...).
- Draw a single incoming arrow (without a source state) pointing to the start state q0.
- Mark each accepting state by a double circle.
- Draw directed edges labeled by input symbols for transitions: from-state --symbol--> to-state. If multiple symbols cause the same transition, group them separated by commas on the same edge, e.g. "0,1".
- If a state has no outgoing transition for some symbol, either draw an arrow to a labelled dead state or state in the text that the dead state exists.
Formulas
δ: Q × Σ → Q — δ is the transition function. Q is the set of states (no unit); Σ is the alphabet.
δ*: Q × Σ* → Q — extended transition function; applies to whole strings.
δ*(q, ε) = q — extended function on empty string; q ∈ Q.
δ*(q, xa) = δ(δ*(q, x), a) — recursion for extended function; x ∈ Σ*, a ∈ Σ.
L(M) = { w ∈ Σ* | δ*(q0, w) ∈ F } — language accepted by DFA M = (Q, Σ, δ, q0, F).
If converting an NFA with n states to DFA by subset construction:
|Q_DFA| ≤ 2^n — number of DFA states at most 2 to the power n.
Complement construction (requires total δ):
L(M_complement) = Σ* \ L(M) when M is complete; M_complement = (Q, Σ, δ, q0, Q \ F).
Worked examples
Example 1 — DFA for last two bits are "01":
- Problem: Construct DFA M over Σ = {0,1} that accepts exactly those strings whose last two symbols are 01.
- Idea: Keep track of the last up to two symbols seen. Use suffix-based state names: qε (start; no input yet or last suffix not relevant), q0 (last symbol 0), q01 (last two symbols 01). q01 is the sole accepting state.
- Formal M = (Q, Σ, δ, qε, F) where Q = {qε, q0, q01}, F = {q01}.
- Transitions (describe to draw):
- From qε: on 0 → q0, on 1 → qε.
- From q0: on 0 → q0, on 1 → q01.
- From q01: on 0 → q0, on 1 → qε.
- Trace input w = 1101 step-by-step using δ*:
- Start at qε.
- Read '1': δ(qε,1) = qε.
- Read '1': δ(qε,1) = qε.
- Read '0': δ(qε,0) = q0.
- Read '1': δ(q0,1) = q01.
- Input ended, current state q01 ∈ F so accept. Answer: accepted.
Example 2 — DFA for number of 1s divisible by 3:
- Problem: Build DFA over Σ = {0,1} that accepts strings with number of 1s ≡ 0 (mod 3).
- Idea: States represent remainder modulo 3 of count of 1s seen: q0 (remainder 0), q1 (remainder 1), q2 (remainder 2). q0 is start and accepting.
- Formal M = (Q, Σ, δ, q0, F) with Q = {q0,q1,q2}, F = {q0}.
- Transitions: on input 0 stay in same state (no change in count of 1s). On input 1 move cyclically q0→q1→q2→q0.
- Draw edges: q0 --0--> q0, q0 --1--> q1, q1 --0--> q1, q1 --1--> q2, q2 --0--> q2, q2 --1--> q0.
- Trace input w = 1101:
- Start q0.
- Read '1' → q1.
- Read '1' → q2.
- Read '0' → q2.
- Read '1' → q0.
- End at q0 ∈ F so accepted.
These examples show the formal transition table or diagram expected in exams and a step-by-step δ* trace.
Common mistakes
- Forgetting to handle the empty string ε (check whether q0 ∈ F).
- Mixing up DFA with NFA: in DFA each transition must go to exactly one state for each symbol.
- Drawing transitions incorrectly when grouping symbols; double-check labels.
For your exam
Typical question types on DFA:
- Definitions: define DFA, δ*, acceptance, language of DFA.
- Short notes: explain difference between DFA and NFA; total (complete) DFA and the dead state; complement construction.
- Derivations / proofs: prove δ* properties by induction; show complement correctness; prove size bound 2^n for subset construction (outline).
- Construction problems: design DFA for a language like "strings ending with a substring", "number of a symbol divisible by k", "contains a substring". A full-marks answer includes: formal 5-tuple, transition diagram (or table), brief correctness argument, and a small trace for 1 example input.
- Minimisation and equivalence are separate topics (Minimisation of DFA, Myhill–Nerode theorem) but exam may ask how many states are enough and to draw minimal DFA.
Quick check
- Give the 5 components of a DFA and explain each in one line.
- If M = (Q, Σ, δ, q0, F) and w ∈ Σ* with δ*(q0, w) = q2, how do you decide if w ∈ L(M)?
- True/False: In a DFA, a single state may have two different outgoing edges labelled the same symbol.
Answers: 1) Q (states), Σ (alphabet), δ (transition function), q0 (start state), F (set of accepting states). 2) w ∈ L(M) iff q2 ∈ F. 3) False — for a DFA a given state and input symbol determine exactly one outgoing transition.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?