Information Technology is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Minimisation of DFA

Minimisation of a DFA means producing the smallest deterministic finite automaton that recognises the same regular language; it is done by removing unreachable states and merging equivalent states using partition refinement (Moore or Hopcroft) and is unique up to isomorphism.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Minimisation of a DFA gives the smallest machine that recognises the same regular language. Engineers use minimal DFAs in lexical analysers, network protocol verification, hardware controllers and any implementation where fewer states reduce memory, speed or power.

Key ideas

  • Definition: a state r ∈ Q is reachable (or accessible) if there exists x ∈ Σ* such that δ*(q0, x) = r. A state not reachable is unreachable (sometimes called inaccessible). Unreachable states can be removed without changing the recognised language.

  • Definition: a DFA is minimal if there is no DFA with fewer states that recognises the same language. Minimal DFAs are unique up to renaming of states (isomorphism): any two minimal DFAs recognising the same language are isomorphic. Also, in any minimal DFA every state is reachable from the start state; otherwise it could be removed to obtain a smaller equivalent DFA.

  • Theorem (Myhill–Nerode, exact statement used in minimisation): Let L ⊆ Σ*. Define relation ≡L on Σ* by x ≡L y iff ∀z ∈ Σ*, xz ∈ L iff yz ∈ L. Then ≡L is an equivalence relation, each equivalence class is a distinct right-invariant class of Σ*, and L is regular iff ≡L has finitely many equivalence classes. Moreover, the minimal number of states in any DFA recognising L equals the number of ≡L equivalence classes, and the DFA with those classes as states is a minimal (canonical) DFA. (Assume Σ finite.)

    • This theorem explains the correctness and optimality of minimisation: merging two states is safe exactly when they represent the same ≡L class.
  • Two standard algorithms to compute a minimal DFA from a given DFA (after removing unreachable states):

    1. Table-filling algorithm (classic classroom method).
      • Start with a table of all unordered pairs of states (p, q). Mark all pairs where one is final and the other is non-final as distinguishable.
      • Repeatedly mark (p, q) if for some input a ∈ Σ the pair (δ(p,a), δ(q,a)) is already marked.
      • When no more marks appear, the unmarked pairs are equivalent and can be merged.
      • Complexity: O(n^2 · |Σ|) time in practice; n = |Q|.
    2. Partition refinement (Hopcroft) algorithm (faster, used in practice).
      • Maintain a partition of Q; initial partition P = {F, Q\F}.
      • Use a worklist of splitter blocks; take a splitter S and an input a, refine every block B into B1 = {q ∈ B | δ(q,a) ∈ S} and B2 = B \ B1 if both non-empty; replace B by (B1, B2) and add the smaller of the two to the worklist (optimisation).
      • Repeat until no refinement possible; blocks are the equivalence classes and each block becomes one state in the minimal DFA.
      • Complexity: O(m log n), where m = |Q|·|Σ| is the number of transitions; for fixed |Σ| this is O(n log n).
  • Correctness sketch for partition methods: Partition refinement computes the coarsest partition that is consistent with transitions and final/non-final separation. Consistency means: if p and q in same block then for every a ∈ Σ, δ(p,a) and δ(q,a) are in the same block; this property exactly matches the definition of equivalence (right-invariance), so the final partition blocks are ≡ classes.

  • Construction of the minimal DFA from blocks: each block B becomes a state [B]; start state is the block containing q0; accepting blocks are those containing at least one accepting state (equivalently exactly those containing accepting states because accepting and non-accepting are initially separated); define δ'([B], a) = [block containing δ(p,a)] for any p ∈ B (well-defined by consistency).

  • Diagram to draw in an answer that asks for the algorithm on a DFA: draw the original DFA with states as circles, label the start state with an incoming arrow, mark final states with double circles. When showing partitions, draw a table or list the blocks as sets {…}; when showing merged result, draw the new DFA with one circle per block and transitions labeled with letters (show how transitions collapse). For the table-filling method draw an upper triangular table of state pairs and mark cells as you discover distinguishability.

Formulas

n = |Q| — n is the number of states in the original DFA; unit: states (count). Applies always.

P0 = {F, Q \ F} — initial partition into accepting and non-accepting states; symbols: F is set of final states, Q is full state set.

δ*: Q × Σ* → Q — extended transition function; δ*(q, ε) = q and δ*(q, xa) = δ(δ*(q, x), a). Symbols: ε is empty string; applies for computing reachability under strings.

Time(Moore) = O(n^2 · |Σ|) — rough time complexity of table-filling; n = |Q|, |Σ| alphabet size.

Time(Hopcroft) = O(m log n) with m = |Q|·|Σ| (the number of transitions); for fixed |Σ|, this is O(n log n).

Minimal states = number of ≡L equivalence classes — minimal number of states equals number of Myhill–Nerode classes for language L.

Worked examples

Example 1 — merge equivalent states (step-by-step partition refinement)

Given DFA: Q = {A, B, C}, Σ = {0,1}, start A, F = {B, C}. Transitions:

  • δ(A,0)=B, δ(A,1)=C
  • δ(B,0)=B, δ(B,1)=C
  • δ(C,0)=B, δ(C,1)=C

Goal: minimise.

Steps (Hopcroft-style in small form):

  1. Remove unreachable states: from A we reach B and C, so all reachable.
  2. Initial partition P0 = {F, Q\F} = {{B, C}, {A}}.
  3. Check consistency: for block {B,C}, for a=0, δ(B,0)=B ∈ {B,C}, δ(C,0)=B ∈ {B,C}; for a=1, δ(B,1)=C ∈ {B,C}, δ(C,1)=C ∈ {B,C}. So {B,C} is consistent and needs no split.
  4. No refinement possible; blocks are {{A}, {B, C}}.
  5. Build minimal DFA: states [A], [B,C]. Start = [A]. Accepting = [B,C]. Transitions: [A]-0->[B,C], [A]-1->[B,C]; [B,C]-0->[B,C], [B,C]-1->[B,C]. This is a 2-state DFA. So B and C merged.

In an exam draw: original three-state DFA with A single circle and B,C double circles; minimal DFA with two states and transitions as above.

Example 2 — table-filling and unreachable removal (common exam question)

Given DFA with Q = {q0, q1, q2, q3}, Σ={a}, start q0, F={q2}. Transitions: q0-a->q1, q1-a->q2, q2-a->q2, q3-a->q3. Here q3 is unreachable.

Steps:

  1. Remove unreachable: q3 removed.
  2. Table of pairs among {q0,q1,q2}: mark pairs where one is final and other not: mark (q0,q2) and (q1,q2).
  3. Check pair (q0,q1): δ(q0,a)=q1, δ(q1,a)=q2; (q1,q2) is marked so mark (q0,q1).
  4. All pairs marked → no two states equivalent. Minimal DFA has states q0,q1,q2.

Write the minimal DFA (same as reachable part of original).

Common mistakes

  • Confusing equivalence of states with equality of transition targets for single symbols — equivalence is about all strings, not only one-step transitions.
  • Using Hopcroft without noting alphabet handling: the O(n log n) claim assumes efficient handling of alphabet; naive implementations may be slower.
  • Marking pairs in the table-filling method incorrectly (confusing ordered vs unordered pairs); always use unordered pairs and a consistent scheme.

For your exam

Typical questions:

  • Give the formal definition of a DFA and define equivalent states.
  • Show minimisation of a small DFA step-by-step (either table method or partition refinement). A full-marks answer draws the DFA, lists reachable states, shows initial partition, each refinement step (table marks or partition splits), resulting blocks, and the final minimal DFA with transitions.
  • State and explain the Myhill–Nerode theorem and how it guarantees uniqueness of the minimal DFA.
  • Compare Moore (table-filling) and Hopcroft algorithms and give their time complexities and when each is preferable.

What full-mark answers include:

  • Clear definitions (bold terms) and formal statements.
  • Correct, fully worked algorithm steps with no missing iteration.
  • Correct final minimal DFA drawn and labelled: states, start arrow, double circles for finals, and transitions.

Quick check

  1. What initial partition do you use when minimising a DFA?
  2. In table-filling, when do you mark a pair (p,q)?
  3. True/False: The minimal DFA for a regular language is unique up to renaming states.

Answers: 1) Partition of Q into {F, Q \ F}. 2) Mark (p,q) if one is final and the other is not, or if for some a ∈ Σ the pair (δ(p,a), δ(q,a)) is already marked. 3) True.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?