**Minimization Algorithm for a DFA**

- Identify and remove the unreachable states. These states are the states with no incoming transition, but only outgoing transition.
- Draw two transition tables T
_{1}and T_{2}where T_{1}contains all rows which contains states from Q-F and T_{2}contains all the states from set F. - 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.
- Find the similar rows from T
_{1}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. - Repeat the above step till all redundant rows have been eliminated.
- Repeat step 4 and 5 for table T
_{2} - 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 q_{3} 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

T_{1}

**
advertisements
**

States | input a | input b |
---|---|---|

q_{0} |
q_{5} |
q_{1} |

q_{1} |
q_{2} |
q_{6} |

q_{4} |
q_{5} |
q_{7} |

q_{5} |
q_{6} |
q_{2} |

q_{6} |
q_{4} |
q_{6} |

q_{7} |
q_{2} |
q_{6} |

T_{2}

q_{2} |
q_{2} |
q_{0} |

Step 4:

Reducing the table by removing indistinguishable states

q_{1} and q_{7} are indistinguishable. Remove q_{7} and replace reference of q_{7} with q_{1}.

q_{0} |
q_{5} |
q_{1} |

q_{1} |
q_{2} |
q_{6} |

q_{4} |
q_{5} |
q_{1} |

q_{5} |
q_{6} |
q_{2} |

q_{6} |
q_{4} |
q_{6} |

Now q_{0} and q_{4} are indistinguishable. Remove q_{4} and replace references of q_{4} with q_{0}.

q_{0} |
q_{5} |
q_{1} |

q_{1} |
q_{2} |
q_{6} |

q_{5} |
q_{6} |
q_{2} |

q_{6} |
q_{0} |
q_{6} |

Step 6 : There is no indistinguishable state in set of final states so they remain unchanged

Step 7: Merging the two sets T_{1} and T_{2} so the final transition table for the DFA is :

q_{0} |
q_{5} |
q_{1} |

q_{1} |
q_{2} |
q_{6} |

*q_{2} |
q_{2} |
q_{0} |

q_{4} |
q_{5} |
q_{1} |

q_{5} |
q_{6} |
q_{2} |

q_{6} |
q_{4} |
q_{6} |

The final DFA after minimization :

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

If you wish to look at all Tutorials and their examples, go to Theory of Computation Tutorials.