MINIMISATION OF DFA is the procedure through which we can obtain minimized DFA which consists of a minimum number of states.

There are two classes of states that can be removed or merged from the original DFA without affecting the language it accepts to minimize it.

• Unreachable states are the states that are not reachable from the initial state of the DFA, for any input string.
• Nondistinguishable states are those that cannot be distinguished from one another for any input string.

Let p and q be two states then (p,q) are equivalent states and this two states in a DFA can be replaced by a single state if  where state p on seeing input a goes to final state implies that state q also goes to the final state.

STEPS TO MINIMIZE DFA:

1. Remove the unreachable states from DFA.
2. Draw the transition table for the remaining states.
3. Now, divide rows of transition table in 2 states as Set-1 consists of all the non-final states and Set-2 contains final states.
4. Search for similar rows(for different sets deriving output states are same on same input symbol)
5. Merge them and repeat the procedure for the rest of the table.
6. Draw the transition diagram for minimized DFA.

EXAMPLE:

Step-I: Delete a state which is unreachable from the initial state. In this problem, there is no dead state, therefore, proceed to next step.

Step-II: Draw the transition table.

Step-III: Try to find out equivalent sets(sets of all non final states and final states)

• [q_0, q_1,q_2,q₃][q₄] (separating final and non-final states into different sets)
• [q₀q₂][q_1,q₃][q₄] (q₀ and q₂ equivalent states)
• [q₀q₂][q₁][q₃][q₄] (q₁ and q₃ will be in different set as they are not equivalent)

Newly formed states after minimizing the DFA are q₀q₂, q₁, q₃, q_4.

Step-IV: Draw the minimized DFA.

​