CD Notes
Complete guide to Deterministic Finite Automata covering formal definition, state transition diagrams, DFA construction, minimization algorithms, and applications in lexical analysis.
Introduction
A Deterministic Finite Automaton (DFA) is the simplest model of computation used extensively in compiler design, particularly in lexical analysis. The word "deterministic" means that for each state and input symbol, there is exactly one transition — no ambiguity in the machine's behavior. DFAs form the computational backbone of every lexical analyzer, efficiently recognizing tokens like keywords, identifiers, and operators.
Formal Definition
A DFA is defined as a 5-tuple: M = (Q, Σ, δ, q₀, F) where:
- Q = finite set of states
- Σ = finite input alphabet
- δ = transition function, δ: Q × Σ → Q
- q₀ = initial/start state, q₀ ∈ Q
- F = set of accepting/final states, F ⊆ Q
The key property is that δ is a total function — it must be defined for every (state, symbol) pair.
State Transition Diagram
| Example | DFA accepting strings over {a, b} that contain "ab" as substring |
| └──b── | [q0] |
| States | q0 = no part of "ab" seen |
Transition Table Representation
| State | 0 | 1 |
|---|---|---|
| →q0 | q1 | q0 |
| q1 | q1 | q2 |
| *q2 | q1 | q0 |
State diagram
DFA Construction Examples
Example 1: DFA for Even Number of a's
| State | a | b |
|---|---|---|
| →*q0 | q1 | q0 |
| q1 | q0 | q1 |
Example 2: DFA for Binary Numbers Divisible by 3
| | | *q0 | q0 | q1 | (remainder 0) |
| Logic | If current number has remainder r, then: |
| - Appending 0 | new value = 2r, remainder = 2r mod 3 |
| - Appending 1 | new value = 2r+1, remainder = (2r+1) mod 3 |
| Test | "110" (decimal 6): |
| q0-1 | q1-1→q0-0→q0 → ACCEPT ✓ (6 mod 3 = 0) |
Extended Transition Function
The extended transition function δ̂ processes strings rather than single characters:
| δ̂: Q × Σ* | Q |
| Base case | δ̂(q, ε) = q |
| Recursive | δ̂(q, wa) = δ(δ̂(q, w), a) |
| Example | For the "even a's" DFA, processing "aba": |
| = q0 ∈ F | ACCEPT |
DFA Minimization
DFA minimization removes redundant states to produce the smallest equivalent DFA. The standard algorithm uses partition refinement (also called Myhill-Nerode theorem application).
Algorithm (Table-Filling / Marking Algorithm)
| State | a | b |
|---|---|---|
| →*A | B | C |
| B | B | D |
| *C | B | C |
| D | B | E |
| *E | B | C |
Example DFA to minimize
Step 2 - Check unmarked pairs
Minimized DFA
| State | a | b |
|---|---|---|
| →*ACE | B | ACE |
| B | B | D |
| D | B | ACE |
DFA vs NFA Comparison
| Feature | DFA | NFA |
|---|---|---|
| Transitions | Exactly one per (state, | Zero, one, or many per |
| symbol) | (state, symbol) | |
| ε-transitions | Not allowed | Allowed |
| Determinism | Fully deterministic | Non-deterministic |
| Implementation | Direct, efficient | Requires backtracking or |
| subset construction | ||
| States | Can be exponential (2^n) | Generally fewer states |
| Time complexity | O(n) for string of len n | O(n×m) where m = states |
| Space | More states possible | Compact representation |
DFA in Lexical Analysis
In compilers, DFAs are used to implement lexical analyzers:
| Source Code | "if (x >= 10)" |
| 'i' | could be identifier or keyword |
| 'f' | matches "if" keyword |
| ' ' | token boundary, emit IF token |
| '(' | emit LPAREN token |
| 'x' | identifier start |
Implementation in Code
Complement and Product Construction
Complement: To build DFA for complement of L, simply swap final and non-final states.
Product Construction (Intersection): Given DFA M1 and M2, build M1 × M2:
- States: Q1 × Q2
- Transitions: δ((q1,q2), a) = (δ1(q1,a), δ2(q2,a))
- Final states: F1 × F2
Dead States and Trap States
A dead state (or trap state) is a non-accepting state from which no accepting state is reachable:
Interview Questions
- Q: What is the maximum number of states in a DFA equivalent to an NFA with n states?
A: 2ⁿ states in the worst case (subset construction). Each state in the DFA corresponds to a subset of NFA states. However, not all 2ⁿ states may be reachable.
- Q: Can every DFA be minimized? Is the minimal DFA unique?
A: Yes, every DFA can be minimized. The minimal DFA (up to state renaming) is unique for any regular language — this is guaranteed by the Myhill-Nerode theorem.
- Q: How does a lexical analyzer handle multiple token patterns?
A: It combines DFAs for all token patterns into a single combined DFA using product construction or by running them in parallel. On reaching a final state, it uses longest-match rule and priority ordering to select the correct token.
- Q: What happens if the transition function is not total?
A: If δ is partial (not defined for some state-symbol pairs), we add a dead/trap state and redirect all undefined transitions there. This makes it a complete DFA without changing the accepted language.
- Q: Why do compilers use DFAs instead of NFAs for tokenization?
A: DFAs provide O(1) time per character (single table lookup) giving O(n) total for a string of length n. NFAs would require tracking multiple states simultaneously (subset simulation), resulting in higher overhead. The one-time cost of NFA-to-DFA conversion is amortized over millions of characters processed.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Deterministic Finite Automata (DFA) in Compiler Design.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.
Search Terms
compiler-design, compiler design, compiler, design, automata, and, formal, languages
Related Compiler Design Topics