1. Minimize the given DFA

Solution:

0^' equivalence: Start by distinguishing final and non-final:   {q1,q3}, {q2,q4,q5,q6}

1'st equivalence: Distinguish states within the groups, to get the next partition:

{q1,q3}, {q4,q6}, {q5}, {q2}

b distinguishes q2, q4:

δ(q2,b) ∈ {q1,q3}, δ(q4,b) ∈ {q2,q4,q5,q6}

b distinguishes q2, q5:

δ(q2,b) ∈ {q1,q3}, δ(q5,b) ∈ {q2,q4,q5,q6}

a distinguishes q4, q5:

δ(q4,a) ∈ {q1,q3}, δ(q5,a) ∈ {q2,q4,q5,q6}

neither a nor b distinguishes (q4,q6)

2^'nd equivalence: We cannot split the two non-singleton groups further, the algorithm terminates.

The minimal DFA has start state {q1,q3}, single final state {q4,q6} with transition function:

Note: How equivalence classes are decided??

The construction of the equivalence classes starts like this:

1. p and q are 0-indistinguishable if they are both final or both non-final. So we start the algorithm with the states divided in two partitions: final and non-final.
2. within each of these two partitions: p and q are 1-distinguishable if there is a symbol σ so that δ(p,σ) and δ(q,σ) are 0-distinguishable, i.e. one is final and the other not. By doing so we further partition each group into sets of 1-indistinguishable states.
3. The idea then is to keep splitting these partitioning sets as follows:
4. p and q within a partition set are k-distinguishable if there is a symbol σ so that δ(p,σ) and δ(q,σ) are (k-1)-distinguishable.
5. At some point, we cannot subdivide the partitions further. At that point terminate the algorithm, because no further step can produce any new subdivision. When we terminate, we have the indistinguishability equivalence classes which form the states of the minimal DFA. The transition from one equivalence class to another is obtained by choosing an arbitrary state in the source class, applying the transition and then taking the entire target class as the target state.