Minimise a DFA
Table filling: mark every distinguishable pair, then merge what is left.
Hopcroft 2e, §4.4.1 and §4.4.3
Source · DFA
Result
Nothing built yet — step forward to watch it appear.
Distinguishability table
| q1 | ||
|---|---|---|
| q2 | ||
| q0 | q1 |
A number is the round in which that pair was found distinguishable. A blank cell is a pair no string can tell apart — those are the states that merge.
Every state is reachable from q0, so the table is built over all 3 of them.
The answer appears at the last step. if you would rather read it than watch it.
How to read itHopcroft 2e, §4.4.1 and §4.4.3
- Unreachable states go first — they are equivalent to nothing and would sit in the table forever.
- Round 0 marks every pair with one accepting state and one not. Later rounds mark a pair whose successors are already marked.
- The number in a cell is the round it was marked in, so the finished table is the proof, not just the answer.