Introduction

Imagine a vending machine with hundreds of internal states — but after careful inspection you discover that half of them behave identically: feed them the same sequence of coins and buttons and they always respond the same way. Those states are indistinguishable, and there is no reason to keep both of them. Merge them, and you get a simpler machine that accepts exactly the same set of inputs.

This is DFA minimization in a nutshell. A Deterministic Finite Automaton (DFA) is a mathematical model of computation that reads a string of symbols one at a time and ends in an accepting or rejecting state. Every DFA recognizes some regular language — the set of strings it accepts. Many different DFAs can recognize the same language, some with far fewer states than others.

The fundamental theorem of automata theory tells us that every regular language has a unique minimal DFA (up to renaming of states). In 1971, computer scientist John Hopcroft published an algorithm that finds this minimal machine in O(nlog⁡n)O(n \log n) time, where n is the number of states. No general-purpose algorithm can do better: the problem has a matching Ω(n log n) lower bound for comparison-based models.

The key insight is breathtaking in its simplicity: two states are distinguishable if there exists some string that leads one to acceptance and the other to rejection. Hopcroft's algorithm works backwards — it starts by separating accepting from non-accepting states and then keeps splitting groups apart whenever a symbol reveals a difference. States that survive without being split are genuinely interchangeable, and the algorithm merges them all at once.

Try It: Partition Refinement

The demo below shows a DFA with 6 states that accepts binary strings ending in 01. States C and E are redundant — they behave identically on every suffix. Click Step to advance Hopcroft's partition refinement one round at a time, or Run All to see the full minimization at once. The final minimal DFA has only 3 states.

<p class="hint">A 6-state DFA accepting binary strings ending in <b>01</b>. States A&amp;D and B&amp;E are redundant pairs — each pair behaves identically on every suffix. Run Hopcroft’s partition refinement to discover and merge them into a 3-state minimal DFA.</p>
<div class="layout">
  <div>
    <div class="panel-label">Original DFA — 6 states</div>
    <canvas id="dfaCanvas" width="310" height="210"></canvas>
  </div>
  <div>
    <div class="panel-label">Minimal DFA — after merging</div>
    <canvas id="minCanvas" width="310" height="210"></canvas>
  </div>
</div>
<div class="partitions" id="partitions"></div>
<div class="status" id="status">Ready. Press Step or Run All.</div>
<div class="btns">
  <button id="stepBtn" type="button">Step</button>
  <button id="runBtn" type="button">Run All</button>
  <button id="resetBtn" type="button" class="ghost">Reset</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.layout { display: flex; gap: 8px; flex-wrap: wrap; margin-bottom: .5rem; }
.layout > div { flex: 1; min-width: 200px; }
.panel-label { font-size: .8rem; font-weight: 600; color: #555; margin-bottom: 2px; }
canvas { border: 1px solid #cdd9e3; border-radius: 8px; background: #f7f9fb;
         display: block; max-width: 100%; }
.partitions { display: flex; flex-wrap: wrap; gap: 6px; margin: .4rem 0; min-height: 32px; }
.block { display: flex; align-items: center; gap: 5px; padding: 4px 10px;
         background: #e8eef3; border: 1px solid #cdd9e3; border-radius: 20px;
         font: 600 12px ui-monospace, monospace; }
.block.merged { background: #d4edda; border-color: #a3cfbb; }
.block .dot { width: 10px; height: 10px; border-radius: 50%; display: inline-block; }
.status { font-size: .95rem; font-weight: 600; margin: .4rem 0; min-height: 1.3em; color: #1d3557; }
.status.done { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .4; cursor: default; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// DFA accepting binary strings ending in "01".
// States A..F (A = start, C and F = accepting):
//   A -0-> B, A -1-> A
//   B -0-> B, B -1-> C   (C = accept: just read 01)
//   C -0-> E, C -1-> D
//   D -0-> E, D -1-> D   (D mirrors A, E mirrors B)
//   E -0-> E, E -1-> F
//   F -0-> E, F -1-> D   (F = accept: accept: mirrors C)
// Redundant pairs: {A,D} and {B,E} — Hopcroft finds them.
// Minimal DFA: q0={A,D}, q1={B,E}, q2={C,F}

const STATES = ['A','B','C','D','E','F'];
const ACCEPT = new Set(['C','F']);
const TRANS = {
  A:{'0':'B','1':'A'},
  B:{'0':'B','1':'C'},
  C:{'0':'E','1':'D'},
  D:{'0':'E','1':'D'},
  E:{'0':'E','1':'F'},
  F:{'0':'E','1':'D'}
};
const ALPHABET = ['0','1'];

// Canvas layout positions (310x210)
const POS = {
  A:{x:30, y:60},
  B:{x:110,y:60},
  C:{x:200,y:60},
  D:{x:30, y:155},
  E:{x:110,y:155},
  F:{x:200,y:155}
};
const STATE_COLORS = {
  A:'#4e79a7', B:'#f28e2b', C:'#59a14f',
  D:'#4e79a7', E:'#f28e2b', F:'#59a14f'
};

// Partition state
let partition = [];
let worklist = [];
let stepLog = [];
let done = false;
let round = 0;

function initPartition(){
  partition = [
    STATES.filter(s => ACCEPT.has(s)),    // [C, F]
    STATES.filter(s => !ACCEPT.has(s))    // [A, B, D, E]
  ];
  worklist = [];
  ALPHABET.forEach(sym => {
    worklist.push([0, sym]);
    worklist.push([1, sym]);
  });
  stepLog = ['Initial: {C,F} (accept) | {A,B,D,E} (reject)'];
  done = false;
  round = 0;
}

function stepOnce(){
  while(worklist.length > 0){
    const [ci, sym] = worklist.shift();
    const C = partition[ci];
    if(!C) continue;
    const cSet = new Set(C);
    const preimage = STATES.filter(s => cSet.has(TRANS[s][sym]));
    if(preimage.length === 0) continue;

    let split = false;
    const newPart = [];
    partition.forEach(B => {
      const inside = B.filter(s => preimage.includes(s));
      const outside = B.filter(s => !preimage.includes(s));
      if(inside.length > 0 && outside.length > 0){
        // smaller half first (Hopcroft’s trick)
        newPart.push(inside); newPart.push(outside);
        split = true;
        stepLog.push(fmt('Round %v%: split {%B%} on ’%sym%’ → {%inside%} | {%outside%}', { v: ++round, B: B.join(','), sym: sym, inside: inside.join(','), outside: outside.join(',') }));
      } else { newPart.push(B); }
    });
    if(split){
      partition = newPart;
      ALPHABET.forEach(a => partition.forEach((_,idx) => worklist.push([idx,a])));
      return false;
    }
  }
  done = true;
  stepLog.push(fmt('Done — %length% blocks → %length%-state minimal DFA', { length: partition.length }));
  return true;
}

// ── Drawing helpers ──────────────────────────────────────────────

function arrow(ctx, x1,y1,x2,y2,label,bend,lox,loy){
  ctx.save();
  ctx.strokeStyle='#555'; ctx.fillStyle='#555'; ctx.lineWidth=1.2;
  ctx.beginPath(); ctx.moveTo(x1,y1);
  var mx=(x1+x2)/2, my=(y1+y2)/2;
  var dx=x2-x1, dy=y2-y1, len=Math.sqrt(dx*dx+dy*dy);
  var bx=mx, by=my;
  if(bend){ bx=mx+bend*(-dy/len); by=my+bend*(dx/len); }
  if(bend){ ctx.quadraticCurveTo(bx,by,x2,y2); } else { ctx.lineTo(x2,y2); }
  ctx.stroke();
  var ang=Math.atan2(y2-by,x2-bx);
  ctx.beginPath();
  ctx.moveTo(x2,y2);
  ctx.lineTo(x2-8*Math.cos(ang-0.4),y2-8*Math.sin(ang-0.4));
  ctx.lineTo(x2-8*Math.cos(ang+0.4),y2-8*Math.sin(ang+0.4));
  ctx.closePath(); ctx.fill();
  ctx.fillStyle='#333'; ctx.font='bold 10px ui-monospace,monospace';
  ctx.fillText(label, bx+(lox||0)-3, by+(loy||0)-4);
  ctx.restore();
}

function selfLoop(ctx,x,y,r,label,dir){
  ctx.save();
  ctx.strokeStyle='#555'; ctx.lineWidth=1.2;
  var ox = dir==='up'?0:(r+10);
  var oy = dir==='up'?-(r+10):0;
  ctx.beginPath(); ctx.arc(x+ox, y+oy, 9, 0, 2*Math.PI); ctx.stroke();
  ctx.fillStyle='#333'; ctx.font='bold 10px ui-monospace,monospace';
  var lx = dir==='up'?x-3:x+r+7;
  var ly = dir==='up'?y-(r+16):y+2;
  ctx.fillText(label, lx, ly);
  ctx.restore();
}

function stateCircle(ctx,x,y,r,color,label,isAccept,isHighlight){
  ctx.save();
  ctx.beginPath(); ctx.arc(x,y,r,0,2*Math.PI);
  ctx.fillStyle = isHighlight ? '#ffd166' : color+'33';
  ctx.fill();
  ctx.strokeStyle = isHighlight ? '#e8a000' : color;
  ctx.lineWidth = isHighlight?2.5:1.8; ctx.stroke();
  if(isAccept){
    ctx.beginPath(); ctx.arc(x,y,r-4,0,2*Math.PI);
    ctx.strokeStyle = isHighlight ? '#e8a000' : color;
    ctx.lineWidth=1.4; ctx.stroke();
  }
  ctx.fillStyle='#222'; ctx.font='bold 13px ui-monospace,monospace';
  ctx.textAlign='center'; ctx.textBaseline='middle';
  ctx.fillText(label,x,y);
  ctx.restore();
}

function drawOriginal(highlight){
  var canvas=document.getElementById('dfaCanvas');
  var ctx=canvas.getContext('2d');
  var R=18;
  ctx.clearRect(0,0,canvas.width,canvas.height);

  // Edges (draw before circles)
  // A -1-> A (self)
  selfLoop(ctx, POS.A.x, POS.A.y, R, '1', 'up');
  // A -0-> B
  arrow(ctx, POS.A.x+R, POS.A.y, POS.B.x-R, POS.B.y, '0', 0, 0, -7);
  // B -0-> B (self)
  selfLoop(ctx, POS.B.x, POS.B.y, R, '0', 'up');
  // B -1-> C
  arrow(ctx, POS.B.x+R, POS.B.y, POS.C.x-R, POS.C.y, '1', 0, 0, -7);
  // C -1-> D (diagonal)
  arrow(ctx, POS.C.x-4, POS.C.y+R, POS.D.x+4, POS.D.y-R, '1', 30, 6, 0);
  // C -0-> E
  arrow(ctx, POS.C.x-R, POS.C.y+4, POS.E.x+R, POS.E.y-4, '0', -14, 0, 0);
  // D -1-> D (self)
  selfLoop(ctx, POS.D.x, POS.D.y, R, '1', 'up');
  // D -0-> E
  arrow(ctx, POS.D.x+R, POS.D.y, POS.E.x-R, POS.E.y, '0', 0, 0, -7);
  // E -0-> E (self)
  selfLoop(ctx, POS.E.x, POS.E.y, R, '0', 'up');
  // E -1-> F
  arrow(ctx, POS.E.x+R, POS.E.y, POS.F.x-R, POS.F.y, '1', 0, 0, -7);
  // F -1-> D
  arrow(ctx, POS.F.x-4, POS.F.y+R, POS.D.x+4, POS.D.y+R, '1', 22, -4, 8);
  // F -0-> E
  arrow(ctx, POS.F.x-R, POS.F.y+4, POS.E.x+R, POS.E.y+4, '0', 16, 0, 8);

  // Start arrow
  ctx.save(); ctx.strokeStyle='#888'; ctx.fillStyle='#888'; ctx.lineWidth=1.4;
  ctx.beginPath(); ctx.moveTo(POS.A.x-R-16,POS.A.y); ctx.lineTo(POS.A.x-R-2,POS.A.y); ctx.stroke();
  ctx.beginPath(); ctx.moveTo(POS.A.x-R-2,POS.A.y); ctx.lineTo(POS.A.x-R-10,POS.A.y-5); ctx.lineTo(POS.A.x-R-10,POS.A.y+5); ctx.closePath(); ctx.fill();
  ctx.restore();

  STATES.forEach(function(s){
    stateCircle(ctx, POS[s].x, POS[s].y, R, STATE_COLORS[s], s, ACCEPT.has(s), highlight && highlight.has(s));
  });
}

function drawMinimal(){
  var canvas=document.getElementById('minCanvas');
  var ctx=canvas.getContext('2d');
  var W=canvas.width, H=canvas.height;
  ctx.clearRect(0,0,W,H);
  if(!done){
    ctx.fillStyle='#aaa'; ctx.font='12px system-ui,sans-serif';
    ctx.textAlign='center'; ctx.textBaseline='middle';
    ctx.fillText('Minimal DFA appears here when done.', W/2, H/2);
    return;
  }
  // 3 blocks: positions in a row
  var R=22;
  var mpos = [{x:55,y:H/2},{x:155,y:H/2},{x:255,y:H/2}];
  var mcolors = ['#4e79a7','#f28e2b','#59a14f'];
  var startBI = partition.findIndex(function(b){ return b.includes('A'); });
  var acceptBI = partition.findIndex(function(b){ return b.some(function(s){ return ACCEPT.has(s); }); });
  // All labels
  var labels = partition.map(function(b){ return b.join('/'); });

  // Draw edges
  partition.forEach(function(blk, bi){
    ALPHABET.forEach(function(sym){
      var target = TRANS[blk[0]][sym];
      var ti = partition.findIndex(function(b){ return b.includes(target); });
      var p1=mpos[bi], p2=mpos[ti];
      if(bi===ti){
        selfLoop(ctx, p1.x, p1.y, R, sym, 'up');
      } else {
        // detect if there’s a reverse edge already to add bend
        var hasPair = partition[ti].some(function(s){ return ALPHABET.some(function(a){ var nx=TRANS[s][a]; return partition.findIndex(function(b){ return b.includes(nx); })===bi; }); });
        var bend = (bi<ti) ? (hasPair ? -16 : 0) : (hasPair ? 16 : 0);
        var lo = (bi<ti) ? -7 : 7;
        arrow(ctx, p1.x+(p1.x<p2.x?R:-R), p1.y, p2.x+(p1.x<p2.x?-R:R), p2.y, sym, bend, 0, lo);
      }
    });
  });

  // Start arrow
  var sp=mpos[startBI];
  ctx.save(); ctx.strokeStyle='#888'; ctx.fillStyle='#888'; ctx.lineWidth=1.4;
  ctx.beginPath(); ctx.moveTo(sp.x-R-16,sp.y); ctx.lineTo(sp.x-R-2,sp.y); ctx.stroke();
  ctx.beginPath(); ctx.moveTo(sp.x-R-2,sp.y); ctx.lineTo(sp.x-R-10,sp.y-5); ctx.lineTo(sp.x-R-10,sp.y+5); ctx.closePath(); ctx.fill();
  ctx.restore();

  partition.forEach(function(blk,bi){
    var p=mpos[bi];
    var isAcc=blk.some(function(s){ return ACCEPT.has(s); });
    stateCircle(ctx, p.x, p.y, R, mcolors[bi], labels[bi], isAcc, false);
  });
}

function renderPartitions(){
  var el=document.getElementById('partitions');
  el.innerHTML='';
  var colors=['#4e79a7','#f28e2b','#59a14f','#e15759','#76b7b2','#edc948'];
  partition.forEach(function(blk,i){
    var d=document.createElement('div');
    var merged = done && blk.length > 1;
    d.className='block'+(merged?' merged':'');
    var sp=document.createElement('span');
    sp.className='dot'; sp.style.background=colors[i%colors.length];
    d.appendChild(sp);
    d.appendChild(document.createTextNode('{'+blk.join(',')+'}'));
    el.appendChild(d);
  });
}

function setStatus(t,cls){
  var s=document.getElementById('status');
  s.textContent=t; s.className='status '+(cls||'');
}

function step(){
  if(done) return;
  var finished=stepOnce();
  var last=stepLog[stepLog.length-1];
  if(finished){
    document.getElementById('stepBtn').disabled=true;
    document.getElementById('runBtn').disabled=true;
    setStatus(last,'done');
  } else { setStatus(last); }
  drawOriginal(null); drawMinimal(); renderPartitions();
}

function runAll(){
  while(!done) stepOnce();
  var last=stepLog[stepLog.length-1];
  document.getElementById('stepBtn').disabled=true;
  document.getElementById('runBtn').disabled=true;
  setStatus(last,'done');
  drawOriginal(null); drawMinimal(); renderPartitions();
}

function reset(){
  initPartition();
  document.getElementById('stepBtn').disabled=false;
  document.getElementById('runBtn').disabled=false;
  setStatus('Ready. Press Step or Run All.');
  drawOriginal(null); drawMinimal(); renderPartitions();
}

document.getElementById('stepBtn').addEventListener('click',step);
document.getElementById('runBtn').addEventListener('click',runAll);
document.getElementById('resetBtn').addEventListener('click',reset);

// Self-test
function accepts(s){
  var state='A';
  for(var i=0;i<s.length;i++) state=TRANS[state][s[i]];
  return ACCEPT.has(state);
}
var tests=[
  {s:'01',exp:true},{s:'001',exp:true},{s:'101',exp:true},{s:'1101',exp:true},
  {s:'',exp:false},{s:'0',exp:false},{s:'1',exp:false},{s:'10',exp:false},
  {s:'00',exp:false},{s:'11',exp:false},{s:'010',exp:false},{s:'011',exp:false}
];
var ok=tests.every(function(t){ return accepts(t.s)===t.exp; });
console.log('DFA self-test:', ok?'PASS':'FAIL');

initPartition();
drawOriginal(null); drawMinimal(); renderPartitions();
Result
Console

Notice how the algorithm starts with the coarsest possible partition — accepting versus non-accepting — and refines it. Each refinement step asks: "given this symbol, do all states in this group go to the same block?" If not, the group splits. When no group can be split further, each surviving block collapses into a single state in the minimal DFA.

The Real Complexity

DFA minimization is a solved problem — Hopcroft's 1971 algorithm achieves the proven-optimal O(nlog⁡n)O(n \log n) bound — yet the journey from the naive approach to that optimum is a masterclass in algorithm design.

Three algorithms, three complexities:

  • Table-filling (O(n2)O(n^{2})): Mark every pair of states (p, q) as distinguishable if one accepts and the other doesn't; then propagate: if symbol a takes p→p' and q→q', and (p', q') is already marked, mark (p, q) too. Simple, correct, but quadratic.
  • Brzozowski's algorithm (O(2n)O(2^{n}) worst case, fast in practice): Reverse the DFA, determinize, reverse again, determinize again. Elegant and often fast, but can produce an exponentially large intermediate machine.
  • Hopcroft's algorithm (O(nlog⁡n)O(n \log n)): Maintain a partition of states and a worklist of (block, symbol) pairs to process. When processing (C, a), find every state whose a-transition lands in C — call this set a−1(C)a^{-1}(C). For each block B that intersects a−1(C)a^{-1}(C) but is not a subset of it, split B into B∩a−1(C)B \cap a^{-1}(C) and B∖a−1(C)B \setminus a^{-1}(C). Add the smaller half to the worklist. The "smaller-half" trick is what buys the log factor.

Why O(nlog⁡n)O(n \log n) is optimal: Hopcroft and others proved that any comparison-based minimization algorithm requires Ω(n log n) time. The proof reduces sorting to minimization: you can encode a sorting problem as a DFA minimization instance such that reading off the minimal DFA's transitions reveals the sorted order. Since sorting needs Ω(n log n) comparisons, so does minimization.

The unique minimal DFA: the Myhill–Nerode theorem guarantees that the minimal DFA is unique (up to state renaming). Two states p and q are Myhill–Nerode equivalent if for every string w, the machine accepts pw iff it accepts qw. The equivalence classes of this relation are exactly the states of the minimal DFA. This is not just a curiosity — it means Hopcroft's output is provably optimal, not merely good.

Related reading: P vs NP and pattern matching both touch the boundary between what finite automata can and cannot compute efficiently.

Where It Matters

A minimal DFA is not just mathematically satisfying — it is often measurably faster and smaller in practice. Anywhere a regular language must be recognized at high speed, minimization pays off:

  • Compiler lexers: every programming language tokenizer is a DFA under the hood. Tools like Flex build a DFA from regular-expression rules; minimizing it before generating C code reduces both table size and cache misses.
  • Network packet filtering: firewalls and intrusion-detection systems match packet payloads against thousands of patterns simultaneously using a single DFA. Minimization is the difference between a table that fits in L2 cache and one that doesn't.
  • Model checking and formal verification: hardware and protocol verification tools encode correctness properties as automata and check whether a system's behavior automaton intersects a "bad" automaton. Minimizing both automata before intersection can shrink the state space by orders of magnitude.
  • Natural language processing: morphological analyzers for highly inflected languages encode tens of thousands of word forms as DFAs. Minimization compresses a 200 000-state raw automaton into a few thousand states without losing a single accepted word.
  • Binary decision diagrams (BDDs): a BDD is essentially a minimized DFA over a Boolean alphabet. The "reduced ordered BDD" that made BDDs practical in the 1980s is just Hopcroft's algorithm applied to Boolean functions.

Minimization also clarifies what a language is: because the minimal DFA is unique, it is a canonical fingerprint of the language. Two regular expressions denote the same language if and only if their minimal DFAs are isomorphic — a decidable, efficient equivalence check that has no analogue for context-free or Turing-complete formalisms.

Conclusion

DFA minimization is one of computer science's rare gift-wrapped results: a problem with a unique correct answer, an algorithm that finds it optimally, and a matching lower bound that proves nothing faster is possible.

Hopcroft's partition-refinement insight — keep splitting groups apart until nothing can move, using the smaller-half trick to bound the work — is a template for algorithm design far beyond automata. The same "split the smaller piece" strategy appears in efficient data structure updates and graph algorithms decades later.

And underneath it all sits the Myhill–Nerode theorem: the minimal DFA is not just a solution, it is the canonical form of the language itself. That is a deeper statement than most optimization problems can claim — the minimum is not merely better, it is unique.

Every time a regex engine, a network filter, or a model checker runs faster because someone minimized its automaton, Hopcroft's 1971 insight is quietly at work.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/dfa-minimization/Content licensed under CC BY-NC 4.0.