If A and B are two states in a DFA, we can combine these two states into {A, B} if they are not distinguishable. Two states are distinguishable, if there is at least one string S, such that one of δ (A, S) and δ (B, S) is accepting and another is not accepting. Hence, a DFA is minimal if and only if all the states are distinguishable.
Algorithm
Step 1: Start
Step 2: All the states Q are divided in two partitions: final states and non-final states and are denoted by P0. All the states in a partition are 0th equivalent. Take a counter k and initialize it with 0.
Step 3: Increment k by 1. For each partition in Pk, divide the states in Pk into two partitions if they are k-distinguishable. Two states within this partition X and Y are k-distinguishable if there is an input S such that δ(X, S) and δ(Y, S) are (k-1)-distinguishable.
Step 4: If Pk ≠ Pk-1, repeat Step 3, otherwise go to Step 5.
Step 5: Combine kth equivalent sets and make them the new states of the reduced DFA.
Step 6: Stop