How to minimize a DFA

Introduction

Minimizing a DFA means converting a given DFA to an equivalent DFA with a minimum number of states.

We can the following two methods to minimize a DFA:

1. The equivalence method

2. The Myhill Nerode method

We will cover the Myhill Nerode method in this answer.

Myhill Nerode method

There are five steps included in this process:

1. A $n \times n$ table is formed where $n$ is the number of states in the DFA. The table will specify all possible combinations of the states.

  Let's consider the following DFA:

The equivalent table for the above DFA is:

The upper half of the table is crossed out as the order of the combination does not matter: $(q_1,q_2) \equiv (q_2,q_1)$

2. Mark the states pairs $(x,y)$where $x$ or $y$ must be a final state. These state pairs are called distinguishable relations.

3. Now for the undistinguishable relationsThe state pairs that are of the same type i.e. both are final or both are non-final states., we take each unmarked state pair and compute $δ$
   ((x,y),s)), where s is the set of the inputs. This function calculates the transition from an initial state to a given input. If the resultant pair from any input is already marked in the table, the state pair is also marked.

  e.g. $δ$
((q_0,q_3),a)) = ((q_0,b),(q_3,b))=(q_2,q_4)

  As $(q_2,q_4)$ is a marked state hence $(q_0,q_3)$ will also be marked.

4. Repeat step 3 until no more relations are left that can be marked. In this case, we mark the boxes depending on the iteration number.

We see that $(q_2,q_0)$ is the only pair that cannot be marked.

5. Check the table column-wise and see which unmarked pairs can be merged.

For example, In column 0, only $q_2$ is unmarked. Therefore, $q_0$ and $q_2$ will be merged. This step is repeated by iterating through all the columns.

The transitions of the merged states will have no conflict and are shown on the DFA.