Deterministic Finite-State Automata (DFA)
A DFA has exactly one transition per state per symbol — no guessing, no ambiguity. Learn its formal definition, build transition tables and diagrams, and trace acceptance on real examples.
Formal Definition of a DFA
A Deterministic Finite Automaton (DFA) is a 5-tuple:
| Component | Description |
|---|---|
| Q | Finite, non-empty set of states |
| Σ | Finite input alphabet |
| δ : Q × Σ → Q | Total transition function — maps every (state, symbol) pair to exactly ONE next state |
| q₀ ∈ Q | Start state |
| F ⊆ Q | Set of accepting (final) states |
The word deterministic means: for every state q and every symbol a, there is exactly one defined next state δ(q, a). No ambiguity. No choices.
Key Property — Totality
The transition function δ must be total: it is defined for every pair (q, a) where q ∈ Q and a ∈ Σ. If a transition is "missing" in a diagram, it implicitly goes to a special dead state (a non-accepting state that loops to itself on every symbol).
This ensures the DFA never "gets stuck" — it always processes the entire input.
Example 1 — DFA for Even Number of 0s
Language: L = { w ∈ {0,1}* | w contains an even number of 0s }
Examples accepted: ε, 1, 11, 00, 010, 0110, 1001, 000011, … (Zero itself is an even count, so ε is accepted)
States
We need to track the parity of 0s seen so far:
- q0 — even number of 0s seen so far (start + accepting state)
- q1 — odd number of 0s seen so far
Transition Diagram
Transition Table
(→ = start state, * = accepting state)
Step-by-Step Traces
Trace 1 — "0110" (should be accepted: two 0s → even)
Trace 2 — "010" (should be rejected: one 0 → odd)
Wait — "010" has two 0s (positions 0 and 2), so it IS accepted. Let's try "0" instead.
Trace on "0" (one zero → odd → rejected):
Trace on "0011" (two zeros → even → accepted):
Example 2 — DFA for Strings Ending in 'ab'
Language: L = { w ∈ {a,b}* | w ends with 'ab' }
Examples accepted: ab, aab, bab, aaab, abab, baab, …
States
We track the suffix seen so far relative to the pattern 'ab':
- q0 — no progress toward 'ab' (start state)
- q1 — have just seen 'a' (one step toward 'ab')
- q2 — have just seen 'ab' (accepting state)
Transition Diagram
Transition Table
Understanding the Transitions
| State | On 'a' | Why | On 'b' | Why |
|---|---|---|---|---|
| q0 | → q1 | 'a' starts the prefix of 'ab' | → q0 | 'b' resets progress |
| q1 | → q1 | another 'a' restarts the 'a' prefix | → q2 | 'ab' complete! |
| q2 | → q1 | after 'ab', a new 'a' starts fresh | → q0 | 'abb' — 'b' after pattern, reset |
Step-by-Step Traces
Trace 1 — "bab" (accepted)
Trace 2 — "abab" (accepted — ends in ab)
Trace 3 — "aba" (rejected — ends in a, not ab)
DFAs in Lexical Analysis
In a real compiler, the lexer is implemented as a DFA that recognises multiple token types simultaneously. The DFA is built by:
- Writing a regular expression for each token type.
- Converting each RE to an NFA (Thompson's construction).
- Merging all NFAs (union) into one combined NFA.
- Converting the combined NFA to a DFA (subset construction).
- Minimising the DFA.
The resulting DFA is huge but runs in O(n) — one state transition per input character.
How the Lexer DFA Works
This is why lexers are so fast — no backtracking, no recursion, just a table lookup per character.