# Theory of Computation – Minimizing a Deterministic Finite Automata

In this tutorial we will learn how to minimize a DFA. It is important to minimize the DFA before its implementation. This saves space taken up by unnecessary states and transitions. For any regular language there exists a DFA with smallest number of states that accepts it. The procedure below will always produce the DFA with the smallest number of states from all sets of DFA that recognizes the language.

Minimization Algorithm for a DFA

1. Identify and remove the unreachable states. These states are the states with no incoming transition, but only outgoing transition.
2. Draw two transition tables T1 and T2 where T1 contains all rows which contains states from Q-F and T2 contains all the states from set F.
3. All trap states are indistinguishable. So we remove all the trap states except for the one with the lowest index and replace the trap states reference with the only trap state left.
4. Find the similar rows from T1 such that the states after transition on a given input are same for those states. From the set of similar rows remove all the rows from the table except the one with the smallest index and make corresponding changes to the table.
5. Repeat the above step till all redundant rows have been eliminated.
6. Repeat step 4 and 5 for table T2
7. Now combine the tables to get the minimized DFA.

This minimization process removes the non-reachable states, trap states and the indistinguishable states.

Question: Using the above procedure minimize the given DFA.

Solution:
Step 1: remove the unreachable states. In the above DFA q3 is the only state that has no incoming edge, so we remove it.
Step 2: There are no trap states in the DFA.
Step 3: Transition tables
T1

States input a input b
q0 q5 q1
q1 q2 q6
q4 q5 q7
q5 q6 q2
q6 q4 q6
q7 q2 q6

T2

 q2 q2 q0

Step 4:
Reducing the table by removing indistinguishable states
q1 and q7 are indistinguishable. Remove q7 and replace reference of q7 with q1.

 q0 q5 q1 q1 q2 q6 q4 q5 q1 q5 q6 q2 q6 q4 q6

Now q0 and q4 are indistinguishable. Remove q4 and replace references of q4 with q0.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
 q0 q5 q1 q1 q2 q6 q5 q6 q2 q6 q0 q6

Step 6 : There is no indistinguishable state in set of final states so they remain unchanged
Step 7: Merging the two sets T1 and T2 so the final transition table for the DFA is :

 q0 q5 q1 q1 q2 q6 *q2 q2 q0 q4 q5 q1 q5 q6 q2 q6 q4 q6

The final DFA after minimization :

Sanfoundry Global Education & Learning Series – 100+ Theory of Computation Tutorials.