CD Notes
A comprehensive review of finite automata concepts essential for compiler design including DFA, NFA, epsilon-NFA, conversions, and applications in lexical analysis.
Overview of Finite Automata
Finite automata are abstract computational machines with a fixed amount of memory (represented by states). They form the theoretical foundation of lexical analysis in compilers. Before diving into compiler construction, a solid understanding of finite automata is essential because every scanner/tokenizer is fundamentally a finite automaton.
Types of Finite Automata
DFA (Deterministic Finite Automaton)
Definition: M = (Q, Σ, δ, q₀, F)
Key properties:
- Exactly ONE transition for each (state, symbol) pair
- No ε-transitions
- δ: Q × Σ → Q is a total function
Transition Table
| State | a | b |
|---|---|---|
| →q0 | q1 | dead |
| q1 | dead | q2 |
| *q2 | q2 | q2 |
| dead | dead | dead |
b a
NFA (Non-deterministic Finite Automaton)
Definition: M = (Q, Σ, δ, q₀, F) where δ: Q × Σ → P(Q)
Key properties:
- Multiple transitions allowed for same (state, symbol)
- Can have zero transitions for some pairs
- Accepts if ANY path leads to final state
| Example | NFA for strings containing "ab" OR "ba" |
| └────── | [q3]────────→[[q4]] |
| └── | [q0] (self-loop to keep looking) |
ε-NFA (NFA with Epsilon Transitions)
Definition: M = (Q, Σ, δ, q₀, F) where δ: Q × (Σ ∪ {ε}) → P(Q)
ε-transitions allow state changes without consuming input.
ε-Closure Computation
| Algorithm | ε-closure(q) |
| 1. Initialize | result = {q} |
| - If u ∉ result | add u to result, push u |
| States | q0, q1, q2, q3 |
| ε-transitions: q0 | q1, q1→q2, q2→q0, q2→q3 |
| Start | {q0}, stack=[q0] |
| Pop q0: δ(q0,ε)={q1} | add q1, push q1 |
| Pop q1: δ(q1,ε)={q2} | add q2, push q2 |
| Pop q2: δ(q2,ε)={q0,q3} | q0 already in set, add q3, push q3 |
| Pop q3: δ(q3,ε)={} | nothing |
| Result | {q0, q1, q2, q3} |
NFA to DFA Conversion (Subset Construction)
| DFA State | a | b |
|---|---|---|
| →{q0} | {q0,q1} | {q0} |
| {q0,q1} | {q0,q1} | {q0,q2} |
| {q0,q2} | {q0,q1} | {q0,q3} |
| *{q0,q3} | {q0,q1} | {q0} |
| State | a | b |
|---|---|---|
| →A | B | A |
| B | B | C |
| C | B | D |
| *D | B | A |
Algorithm
Example NFA
Subset Construction
Regular Expressions to NFA (Thompson's Construction)
Base cases
ε: →[i]──ε──→[[f]]
a: →[i]──a──→[[f]]
Union (r|s):
ε──→[NFA for r]──ε
/ \
→[i]──< >──→[[f]]
\ /
ε──→[NFA for s]──ε
Concatenation (rs)
→[NFA for r]──ε──→[NFA for s]
Kleene Star (r*):
ε
┌────────────────────┐
│ ε ε │
→[i]──→[start r]──→[end r]──→[[f]]
│ ↑
└───────────ε──────────────┘
Example: (a|b)*abb
Step 1: Build NFA for (a|b)
Step 2: Apply * to get (a|b)*
Step 3: Concatenate with a, b, b
DFA Minimization Review
| S | 0 | 1 |
|---|---|---|
| A | B | C |
| B | B | D |
| C | B | C |
| D | B | E |
| E | B | C |
Partition Refinement Algorithm
For each input symbol a
Example
Equivalence of DFA, NFA, and ε-NFA
All three models recognize exactly the class of regular languages:
Applications in Compiler Design
Token Recognition
| Token patterns | Regular Expressions → NFA → DFA → Scanner |
| IF | "if" |
| ID | [a-z][a-z0-9]* |
| NUM | [0-9]+ |
| PLUS | "+" |
| ASSIGN | "=" |
| EQ | "==" |
| Priority | keywords > identifiers > operators |
| Longest match | "iffy" is ID, not IF followed by error |
Lexer Generator Pipeline
Limitations of Finite Automata
Finite automata CANNOT recognize:
- Balanced parentheses: {aⁿbⁿ | n ≥ 0}
- Palindromes: {ww^R | w ∈ {a,b}*}
- Matching constructs requiring counting
These require pushdown automata (for CFLs) or Turing machines.
Key Theorems
- Myhill-Nerode Theorem: A language is regular iff it has a finite number of equivalence classes under the indistinguishability relation.
- Pumping Lemma for Regular Languages: If L is regular, there exists p such that any w ∈ L with |w| ≥ p can be written as w = xyz where |xy| ≤ p, |y| ≥ 1, and xyⁱz ∈ L for all i ≥ 0.
- Closure Properties: Regular languages are closed under union, intersection, complement, concatenation, Kleene star, reversal, and homomorphism.
Interview Questions
- Q: What is the difference between DFA and NFA in terms of computational power?
A: They have identical computational power — both recognize exactly the regular languages. The difference is representational: NFAs can be more compact (fewer states) but DFAs are faster to simulate (O(1) per character vs tracking multiple states).
- Q: Why do we convert NFA to DFA for lexical analysis?
A: Lexical analysis processes every character of source code — it must be extremely fast. A DFA gives O(1) time per character (single table lookup), while simulating an NFA requires maintaining a set of current states. The conversion cost is paid once at compile-time of the compiler itself.
- Q: Can a DFA have more states than the equivalent NFA?
A: Yes, exponentially more. An NFA with n states may require up to 2ⁿ states in the equivalent DFA. A classic example: NFA for "nth character from end is 'a'" needs n+1 states, but equivalent DFA needs 2ⁿ states.
- Q: How does the longest-match rule work in a DFA-based scanner?
A: The scanner keeps reading characters as long as transitions exist. It remembers the last accepting state reached. When no transition is possible (or input ends), it backtracks to the last accepting state and emits that token. This ensures "integer" is recognized as one ID token, not "int" keyword plus "eger" ID.
- Q: What is a dead state and when is it useful?
A: A dead state is a non-accepting state with all transitions pointing back to itself — once entered, there is no escape to an accepting state. It makes the DFA complete (total function) and helps the scanner detect errors early.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Finite Automata Review for 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