DFA minimization, closure and decision procedures
Goals
Decide when two states carry the same future information, minimize a complete DFA, and use product constructions to answer language questions. All complements use a fixed alphabet Σ. A language is regular precisely when some DFA recognizes it; equivalent NFAs or classical regular expressions describe the same class.
1. Equivalence depends on all suffixes
States p,q are equivalent if for every z∈Σ, δ(p,z) is final exactly when δ*(q,z) is final. A single distinguishing suffix proves inequivalence. Same finality is necessary, but not sufficient. Remove unreachable states before reporting the size of a minimal accessible DFA.
Partition refinement begins with F and Q\F, dropping empty blocks. Split a block if its states transition on some symbol into different blocks. Repeat until stable. States remaining together have identical future acceptance; collapse each block into one state. The resulting complete minimal accessible DFA is unique up to renaming states.
Worked example over {0,1}: states A,B,C,D; start A; finals C,D. A has 0→B,1→C; B has 0→B,1→D; C has 0→B,1→C; D has 0→B,1→D. All four are reachable. Initial blocks {A,B},{C,D} are already stable: 0 always goes to the first block and 1 to the second. The minimal DFA has two states and recognizes strings ending in 1. A and B have different names and paths to them, yet the same future behavior.
2. Lower bounds by distinguishable prefixes
For L={w∈{a}*:|w| is divisible by m}, m≥1, consider ε,a,…,a^(m−1). For distinct residues i,j, append a^((m−i) mod m). The first prefix reaches a length divisible by m; the second does not. Thus the m prefixes require distinct states. A residue-counter construction uses m states, proving exact minimality. Counting states in one construction proves only an upper bound until a matching lower bound is established.
More generally, define x~L y iff for all z, xz∈L iff yz∈L. Myhill–Nerode says L is regular exactly when this relation has finitely many classes; their number is the minimal complete DFA size. For {a^n b^n:n≥0}, prefixes a^i are pairwise distinguishable by b^i, giving infinitely many classes.
3. Closure by construction
For DFAs M1,M2 over the same alphabet, product states (p,q) track both machines and update both on each symbol. For intersection require both components final; for union require at least one; for symmetric difference require exactly one. At most |Q1||Q2| states occur, but this need not be the minimal count. Difference L1\L2 uses final/nonfinal in that order.
Regular languages are closed under union, intersection, complement, difference, concatenation, star and reversal. For concatenation/star/reversal an ε-NFA construction is convenient; determinize if a DFA is needed. Reversing a DFA's arrows generally gives an NFA with potentially multiple starting choices, handled by a fresh ε-start, not automatically a DFA.
4. Decision procedures with worked witness
DFA emptiness is graph reachability: is some final state reachable from the start? If yes, labels along that path give a witness. Finiteness holds exactly when there is no directed cycle that is both reachable from the start and can reach a final state. DFA edges consume symbols, so repeatedly traversing such a cycle produces arbitrarily long accepted words.
Equivalence of two DFAs reduces to emptiness of their symmetric-difference product. For M1 accepting even length and M2 accepting lengths divisible by 3 over {a}, ε is accepted by both, a by neither, but aa by M1 only. Therefore aa is a counterexample and the languages are unequal. Testing a finite list of strings without such an exhaustive construction does not prove equality.
Pitfalls
- Complement requires total transitions and a common alphabet.
- An unreachable accepting state does not make the language nonempty.
- A reachable cycle does not imply infinitude if no final state is reachable from it.
- Two equivalent automata can have different state counts; only minimal complete accessible versions must match in size.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. Two states are equivalent when they agree on:
A. Their names B. Only ε C. Every possible suffix D. Only suffixes of length one
Answer: C
A: Names carry no language meaning.
B: Equal finality alone is insufficient.
C: This is the definition of future equivalence.
D: Longer suffixes may distinguish states.
P02. The worked four-state DFA minimizes to how many states?
A. 1 B. 2 C. 3 D. 4
Answer: B
A: It accepts 1 but rejects ε, so one state cannot suffice.
B: Stable blocks are {A,B} and {C,D}.
C: No third future behavior exists.
D: Equivalent states can be merged.
P03. Minimum complete DFA states for unary lengths divisible by 5?
A. 4 B. 5 C. 6 D. 32
Answer: B
A: Five residues are pairwise distinguishable.
B: Five residues give both construction and lower bound.
C: An extra sink is unnecessary for this total counter.
D: The subset bound is irrelevant here.
P04. A DFA language is infinite exactly when there is a cycle:
A. Anywhere in the graph B. Reachable from the start only C. That can reach a final only D. Reachable from start and able to reach a final
Answer: D
A: Unreachable or dead cycles do not contribute accepted words.
B: The cycle may never lead to acceptance.
C: The cycle may be unreachable.
D: Repeat that consuming cycle before continuing to a final.
P05. Which product final condition decides inequivalence by nonemptiness?
A. Both components final B. Neither final C. Exactly one final D. First final regardless of second
Answer: C
A: This tests intersection.
B: This tests shared rejection.
C: A witness belongs to one language but not the other.
D: This ignores the second language.
P06. Which string distinguishes even unary length from length divisible by 3?
A. ε B. a C. aa D. aaaaaa
Answer: C
A: Both accept zero length.
B: Both reject length one.
C: Only the even-length machine accepts length two.
D: Both accept length six.
Sources and scope
Aligned to the 2026 course. This lesson covers the stated slice, not the entire Theory of Computation syllabus. All numerical examples and questions are original. No claim of 2027 completeness.
Sign in to keep your progress. Sign in