Finite Automata
Introduction
Finite automata are mathematical models of computation that describe abstract machines with a finite number of states. They are the simplest computational model in the automata theory hierarchy and serve as the foundation for understanding more complex models of computation. Finite automata are widely used in compiler design, text processing, network protocols, and digital circuit design.
Learning Objectives
By the end of this reading, you will be able to:
- Understand and construct deterministic finite automata (DFA)
- Understand and construct nondeterministic finite automata (NFA)
- Draw and interpret state diagrams
- Convert NFAs to DFAs using subset construction
- Prove the equivalence of DFAs and NFAs
- Minimize DFAs using state reduction techniques
- Apply finite automata to solve practical problems
Deterministic Finite Automata (DFA)
Formal Definition
A deterministic finite automaton (DFA) is a 5-tuple M = (Q, Σ, δ, q₀, F) where:
- Q is a finite set of states
- Σ is a finite alphabet (set of input symbols)
- δ: Q × Σ → Q is the transition function
- q₀ ∈ Q is the start state
- F ⊆ Q is the set of accept (final) states
The DFA starts in state q₀ and reads input symbols from left to right. For each symbol, it transitions to a new state according to δ. After reading the entire input string, the DFA accepts if it ends in a state in F; otherwise, it rejects.
Key Properties of DFAs
- Deterministic: For each state and input symbol, there is exactly one next state
- Complete: The transition function is defined for all state-symbol pairs
- No memory: The DFA can only remember a finite amount of information (encoded in states)
Example 1: Binary Strings Ending in "01"
Let's construct a DFA that accepts all binary strings ending in "01".
Informal description: The DFA must remember the last two symbols seen.
States:
- q₀: Start state (no symbols seen yet)
- q₁: Last symbol was 0
- q₂: Last two symbols were 01 (accept state)
- q₃: Last symbol was 1 (but not preceded by 0)
Formal specification:
- Q = {q₀, q₁, q₂, q₃}
- Σ = {0, 1}
- q₀ = q₀ (start state)
- F = {q₂} (accept states)
- δ is defined by:
δ(q₀, 0) = q₁ δ(q₀, 1) = q₃
δ(q₁, 0) = q₁ δ(q₁, 1) = q₂
δ(q₂, 0) = q₁ δ(q₂, 1) = q₃
δ(q₃, 0) = q₁ δ(q₃, 1) = q₃
State diagram:
0 1 0
┌────┐ ┌────┐ ┌────┐
│ │ │ │ │ │
▼ │ │ ▼ │ │
┌──────┐ ┌──────┐ ┌──────┐
→ │ q₀ │ │ q₁ │ │ (q₂) │
└──────┘ └──────┘ └──────┘
│ 1 │ 1 │ 1
│ └────────►│
│ ┌─────────┘
▼ 0 │ 0
┌──────┐◄───┘
│ q₃ │
└──────┘
│
└──► (loops on 1)
Trace examples:
- Input "101": q₀ →(1)→ q₃ →(0)→ q₁ →(1)→ q₂ ✓ (accept)
- Input "110": q₀ →(1)→ q₃ →(1)→ q₃ →(0)→ q₁ ✗ (reject)
Example 2: Even Number of 0s and 1s
Construct a DFA that accepts binary strings with an even number of both 0s and 1s.
States (we need to track parity of both 0s and 1s):
- q₀₀: even 0s, even 1s (accept)
- q₀₁: even 0s, odd 1s
- q₁₀: odd 0s, even 1s
- q₁₁: odd 0s, odd 1s
Formal specification:
- Q = {q₀₀, q₀₁, q₁₀, q₁₁}
- Σ = {0, 1}
- q₀ = q₀₀
- F = {q₀₀}
- Transition function:
0 1
q₀₀ → q₁₀ q₀₁
q₀₁ → q₁₁ q₀₀
q₁₀ → q₀₀ q₁₁
q₁₁ → q₀₁ q₁₀
State diagram:
0 0
┌────────┐ ┌────────┐
│ │ │ │
▼ │ │ ▼
┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐
→ │(q₀₀)│ │ q₁₀ │ │ q₀₁ │ │ q₁₁ │
└─────┘ └─────┘ └─────┘ └─────┘
│ │ ▲ ▲ │ │ ▲
└────────┘ │ │ └────┘ │
1 └────┘ 1 │
1 │
└──────────────────┘
0
Nondeterministic Finite Automata (NFA)
Formal Definition
A nondeterministic finite automaton (NFA) is a 5-tuple M = (Q, Σ, δ, q₀, F) where:
- Q is a finite set of states
- Σ is a finite alphabet
- δ: Q × Σ_ε → P(Q) is the transition function (where Σ_ε = Σ ∪ {ε} and P(Q) is the power set of Q)
- q₀ ∈ Q is the start state
- F ⊆ Q is the set of accept states
Key Differences from DFAs
- Nondeterminism: Multiple possible next states for a given state-symbol pair
- ε-transitions: Can transition between states without consuming input
- Acceptance: Accepts if any computation path leads to an accept state
Example 3: Binary Strings Containing "101"
Construct an NFA that accepts all binary strings containing the substring "101".
Intuition: Stay in the start state until we guess that "101" is beginning. Then verify.
Formal specification:
- Q = {q₀, q₁, q₂, q₃}
- Σ = {0, 1}
- q₀ = q₀
- F = {q₃}
Transition function:
δ(q₀, 0) = {q₀}
δ(q₀, 1) = {q₀, q₁} ← nondeterministic choice!
δ(q₁, 0) = {q₂}
δ(q₂, 1) = {q₃}
δ(q₃, 0) = {q₃}
δ(q₃, 1) = {q₃}
State diagram:
0,1 1 0 1 0,1
┌────────┐ ┌────┐ ┌────┐ ┌────────┐
│ │ │ │ │ │ │ │
▼ │ │ ▼ │ ▼ │ │
┌──────┐ │ ┌──────┐ ┌──────┐ ┌──────┐ │
→ │ q₀ │──┘ │ q₁ │ │ q₂ │ │ (q₃) │──┘
└──────┘ └──────┘ └──────┘ └──────┘
└──────────►│
1
Computation example for "0101":
Nondeterministic branches:
Path 1: q₀ →(0)→ q₀ →(1)→ q₀ →(0)→ q₀ →(1)→ q₀ ✗
Path 2: q₀ →(0)→ q₀ →(1)→ q₁ →(0)→ q₂ →(1)→ q₃ ✓
...other paths possible...
Since at least one path accepts, the NFA accepts "0101".
ε-Transitions (Epsilon Transitions)
An ε-transition allows the NFA to change states without consuming any input symbol.
Example 4: NFA accepting strings of 0s with length divisible by 2 or 3.
┌──────┐ 0 ┌──────┐ 0 ┌──────┐
│ (q₀) │────►│ q₁ │────►│ (q₂) │
└──────┘ └──────┘ └──────┘
│ ε │ 0
│ ▼
│ ┌──────┐
│ │ q₀ │ (back to start)
│ └──────┘
│ ε
▼
┌──────┐ 0 ┌──────┐ 0 ┌──────┐ 0 ┌──────┐
│ q₃ │────►│ q₄ │────►│ q₅ │────►│ (q₆) │
└──────┘ └──────┘ └──────┘ └──────┘
│ 0
▼
┌──────┐
│ q₃ │ (back)
└──────┘
The ε-transitions from q₀ allow the NFA to "choose" which pattern to match.
Equivalence of DFAs and NFAs
Theorem: NFA-to-DFA Equivalence
Theorem: For every NFA N, there exists a DFA D such that L(N) = L(D).
Proof Strategy: Use the subset construction (also called powerset construction).
Subset Construction Algorithm
Given an NFA N = (Q_N, Σ, δ_N, q₀, F_N), construct DFA D = (Q_D, Σ, δ_D, {q₀}, F_D) where:
- Q_D = P(Q_N) (each DFA state is a set of NFA states)
- δ_D(R, a) = ⋃_{q∈R} δ_N(q, a) for R ⊆ Q_N and a ∈ Σ
- F_D = {R ∈ Q_D : R ∩ F_N ≠ ∅} (accept if any NFA state in the set is accepting)
When ε-transitions are present, we need the ε-closure operation:
ε-closure(q) = set of states reachable from q using only ε-transitions (including q itself)
Example 5: Converting NFA to DFA
Consider the NFA from Example 3 (strings containing "101").
NFA states: {q₀, q₁, q₂, q₃}
Subset construction:
Start with {q₀}. Compute reachable states:
DFA State Input 0 Input 1
{q₀} {q₀} {q₀, q₁}
{q₀, q₁} {q₀, q₂} {q₀, q₁}
{q₀, q₂} {q₀} {q₀, q₁, q₃}
{q₀, q₁, q₃} {q₀, q₂, q₃} {q₀, q₁, q₃}
{q₀, q₂, q₃} {q₀, q₃} {q₀, q₁, q₃}
{q₀, q₃} {q₀, q₃} {q₀, q₁, q₃}
Accept states: Any set containing q₃.
This DFA has 6 states instead of the potentially 2⁴ = 16 states.
Complexity Analysis
- Worst case: NFA with n states → DFA with 2ⁿ states
- Best case: NFA with n states → DFA with n states
- The exponential blowup is unavoidable for some languages
DFA Minimization
Motivation
A DFA may have redundant states that can be merged without changing the language it accepts. Minimization produces an equivalent DFA with the fewest possible states.
The Myhill-Nerode Theorem
Definition: Two strings x and y are distinguishable with respect to language L if there exists a string z such that exactly one of xz and yz is in L.
Theorem (Myhill-Nerode): The following are equivalent:
- L is regular
- L is the language of some DFA
- The set of equivalence classes of the relation ≡_L is finite
Where x ≡_L y iff for all strings z, xz ∈ L ⟺ yz ∈ L.
Table-Filling Algorithm
This algorithm finds and merges equivalent states.
Algorithm:
- Create a table with an entry for each pair of states (p, q)
- Mark distinguishable pairs:
- Initially mark all pairs (p, q) where exactly one of p, q is in F
- Iterate until no new marks:
- For each unmarked pair (p, q) and each symbol a:
- If (δ(p, a), δ(q, a)) is marked, mark (p, q)
- For each unmarked pair (p, q) and each symbol a:
- Merge all unmarked pairs (they are equivalent)
Example 6: Minimizing a DFA
Consider a DFA with states {q₀, q₁, q₂, q₃, q₄, q₅} where F = {q₃, q₅}:
Transition table:
0 1
q₀ → q₁ q₂
q₁ → q₃ q₄
q₂ → q₄ q₃
q₃ → q₃ q₃ (accept)
q₄ → q₅ q₅
q₅ → q₅ q₅ (accept)
Step 1: Initial marking
q₀ q₁ q₂ q₃ q₄
q₁
q₂
q₃ X X X
q₄ X
q₅ X X X X
Step 2: Iterate
- (q₀, q₁): δ(q₀,0)=q₁, δ(q₁,0)=q₃ → (q₁,q₃) marked ✓
- (q₀, q₂): δ(q₀,1)=q₂, δ(q₂,1)=q₃ → (q₂,q₃) marked ✓
- (q₁, q₂): δ(q₁,0)=q₃, δ(q₂,0)=q₄ → (q₃,q₄) marked ✓
- (q₃, q₅): Both accept, δ(q₃,0)=q₃, δ(q₅,0)=q₅ → check (q₃,q₅) unmarked ✓
After iterations:
- Equivalent pairs: (q₃, q₅)
- Merge q₃ and q₅ into a single state
Minimized DFA: 5 states instead of 6.
Uniqueness of Minimal DFA
Theorem: For any regular language L, there exists a unique (up to isomorphism) minimal DFA that recognizes L.
This minimal DFA is called the canonical automaton for L.
Properties of Regular Languages
Closure Properties
Regular languages are closed under:
- Union: If L₁ and L₂ are regular, so is L₁ ∪ L₂
- Concatenation: If L₁ and L₂ are regular, so is L₁L₂ = {xy : x ∈ L₁, y ∈ L₂}
- Kleene star: If L is regular, so is L* = {x₁x₂...xₖ : k ≥ 0, each xᵢ ∈ L}
- Intersection: If L₁ and L₂ are regular, so is L₁ ∩ L₂
- Complement: If L is regular, so is L̄ = Σ* \ L
- Difference: If L₁ and L₂ are regular, so is L₁ \ L₂
Proof sketch (Union): Given DFAs D₁ and D₂, construct NFA with ε-transitions from new start state to both D₁ and D₂ start states.
Proof sketch (Intersection): Given DFAs D₁ = (Q₁, Σ, δ₁, q₁, F₁) and D₂ = (Q₂, Σ, δ₂, q₂, F₂), construct D = (Q₁ × Q₂, Σ, δ, (q₁, q₂), F₁ × F₂) where δ((p, q), a) = (δ₁(p, a), δ₂(q, a)).
This is called the product construction.
Decision Problems
Given a DFA D, we can decide:
- Emptiness: Is L(D) = ∅? (Check if any accept state is reachable from start)
- Membership: Is w ∈ L(D)? (Simulate D on w)
- Finiteness: Is |L(D)| < ∞? (Check for cycles reachable from start that reach accept states)
- Equivalence: Given DFAs D₁ and D₂, is L(D₁) = L(D₂)? (Minimize both and check structural equality)
All these problems are decidable for DFAs.
Applications of Finite Automata
1. Lexical Analysis
Compilers use DFAs to recognize tokens:
Example tokens:
- Identifiers: [a-zA-Z][a-zA-Z0-9]*
- Numbers: [0-9]+
- Keywords: if, while, for, etc.
Each token type corresponds to a DFA, and these are combined into a single DFA.
2. Pattern Matching
Text editors and tools (grep, sed) use NFAs/DFAs to implement regular expressions.
3. Protocol Verification
Network protocols can be modeled as finite state machines:
TCP Connection States:
CLOSED → LISTEN → SYN_SENT → ESTABLISHED → FIN_WAIT → CLOSED
4. Digital Circuit Design
Sequential circuits (circuits with memory) are finite state machines:
- Flip-flops store state
- Combinational logic computes next state and output
Exercises
Basic Exercises
DFA Construction: Design a DFA over Σ = {a, b} that accepts strings where:
- a) The number of a's is odd
- b) Every a is immediately followed by at least one b
- c) The string contains the substring "aba"
State Diagram Interpretation: Given the following DFA, describe the language it accepts:
┌────┐ a ┌────┐ b ┌────┐
→ │ q₀ │─────►│ q₁ │─────►│(q₂)│
└────┘ └────┘ └────┘
│ b │ a │ a,b
└───────────┘ │
▼
┌────┐
│ q₃ │
└────┘
│
└──► (loops on a,b)
- NFA Construction: Design an NFA (with at most 4 states) that accepts strings over {0, 1} that end in "00" or contain "101".
Intermediate Exercises
- NFA to DFA Conversion: Convert the following NFA to an equivalent DFA using subset construction:
States: {q₀, q₁, q₂}, Alphabet: {a, b}, Start: q₀, Accept: {q₂}
δ(q₀, a) = {q₀, q₁}
δ(q₀, b) = {q₀}
δ(q₁, b) = {q₂}
δ(q₂, a) = {q₂}
δ(q₂, b) = {q₂}
- DFA Minimization: Minimize the following DFA:
States: {A, B, C, D, E, F}, Accept: {C, F}
δ(A, 0) = B, δ(A, 1) = C
δ(B, 0) = A, δ(B, 1) = D
δ(C, 0) = E, δ(C, 1) = F
δ(D, 0) = E, δ(D, 1) = F
δ(E, 0) = E, δ(E, 1) = E
δ(F, 0) = F, δ(F, 1) = F
- Product Construction: Given DFA D₁ accepting binary strings with even number of 0s and DFA D₂ accepting binary strings with even number of 1s, construct a DFA accepting strings with both properties using product construction.
Advanced Exercises
Equivalence Proof: Prove formally that every NFA with ε-transitions can be converted to an NFA without ε-transitions (and hence to a DFA).
Lower Bound: Prove that any DFA accepting the language L = {w ∈ {0,1}* : the nth symbol from the end is 1} must have at least 2ⁿ states. (Hint: Use the Myhill-Nerode theorem and show that all strings of length n are pairwise distinguishable.)
Closure Proof: Prove that regular languages are closed under the reverse operation. That is, if L is regular, then L^R = {w^R : w ∈ L} is also regular. (Hint: Reverse all transitions in an NFA and swap start/accept states.)
Minimization Correctness: Prove that the table-filling algorithm correctly identifies all pairs of equivalent states. Show both:
- a) If two states are not marked, they are equivalent
- b) If two states are marked, they are distinguishable
Application Problem: Design a DFA that accepts binary strings representing numbers divisible by 3 (treat the string as a binary number). Prove that your DFA is correct.
Non-regularity Setup: Consider the language L = {0ⁿ1ⁿ : n ≥ 0}. Try to construct a DFA for this language and explain why you cannot succeed. (We'll prove this language is non-regular in the next reading using the pumping lemma.)
Summary
In this reading, we covered the fundamentals of finite automata:
- DFAs are deterministic, complete, and memory-less computational models
- NFAs introduce nondeterminism and ε-transitions for more flexible design
- Equivalence: NFAs and DFAs recognize the same class of languages (regular languages)
- Conversion: Subset construction converts NFAs to DFAs (potential exponential blowup)
- Minimization: Every DFA can be minimized to a unique canonical form
- Properties: Regular languages have strong closure properties and decidable questions
- Applications: Finite automata are used in compilers, text processing, protocols, and circuits
Key Insights:
- Nondeterminism doesn't add computational power but can make design easier
- State minimization is algorithmic and produces a unique minimal automaton
- The number of states captures the "complexity" of regular language recognition
Limitations:
- Finite automata cannot count (beyond a fixed bound)
- They cannot recognize languages like {0ⁿ1ⁿ : n ≥ 0} or balanced parentheses
- These limitations will be addressed with more powerful models (pushdown automata, Turing machines)
Next Steps
In the next reading, we'll explore Regular Languages and Expressions, where we'll:
- Define regular expressions as an algebraic notation for regular languages
- Prove equivalence between regular expressions and finite automata
- Use the pumping lemma to prove languages are non-regular
- Study algebraic properties and minimization of regular expressions
Continue to Regular Languages and Expressions →
References and Further Reading
- Sipser, Michael. "Introduction to the Theory of Computation" (Chapter 1)
- Hopcroft, John E., Rajeev Motwani, and Jeffrey D. Ullman. "Introduction to Automata Theory, Languages, and Computation" (Chapters 2-4)
- Kozen, Dexter C. "Automata and Computability" (Chapters 4-10)
- Sudkamp, Thomas A. "Languages and Machines" (Chapters 2-5)