Minimization of DFA is a highly important topic from GATE perspective. This article will provide a brief outline of the Minimization process, Steps required to Minimize the Automata and also describe solved examples.
In order to assist you in your GATE preparation , We provide daily Free Quiz (chapter wise) , study tips , preparation Tips for GATE 2017 preparation .
You can subscribe and get daily FREE Quiz (Chapter Wise) , study tutorials and tips delivered on your personal email id to crack the upcoming GATE Exam.
What is Minimization?
Minimization is defined as the process of transforming a given deterministic finite automaton (DFA) into an equivalent DFA with minimum number of states.
What is the Need for Minimization?
It is essential to minimize a DFA before its implementation. Minimization is done in order to save space taken up by redundant states and transitions.
Minimization helps in removal of nonreachable states, trap states and the indistinguishable states.
Steps for Minimization of DFA
 First of all, identify and remove the unreachable states. Unreachable states are the ones which have no incoming transition but only have an outgoing transition.
important article : Most Important Topics For GATE2017 (CSE)  guaranteed Results
2. (p,q) are two states and they are equivalent if the following conditions are satisfied:
δ(p,w) ε F which implies that a state p after undergoing transition on input string w gives a state belonging to set of final states F and δ (q,w) ε F which implies that a state q after undergoing transition on input string w gives a state which belongs to Set of Final States F.
3. Find 0equivalent
Separate the nonfinal states from the final states
When Mod (w) = 0, then (p,q) are 0equivalent
must read : 6 Month Study Plan/TimeTable To Crack GATE (CS) 2017 By Experts
4. Find 1Equivalent
In this, we take a pair of initial and each corresponding state in the set of nonfinal states and check whether they are equivalent or not.We place the equivalent states in one set and place all nonequivalent states in different sets.
5. Find 2Equivalent
From the set obtained in 1Equivalent, proceed by checking the states belonging to the same set.The process of finding equivalents continues till we obtain the minimized DFA.
Solved Examples on Minimization of DFA
 Find the minimized DFA for the figure shown below:
Soln: In this question, q_{0} is the initial state and q_{4} is the final state.
Step 1 : First, draw the transition table. Next, we need to remove the unreachable or inaccessible states.
State 
Transition Function


a 
b 

q_{0} 
q_{1} 
q_{2} 
q_{1} 
q_{1} 
q_{3} 
q_{2} 
q_{1} 
q_{2} 
q_{3} 
q_{1} 
q_{4} 
q_{4} 
q_{1} 
q_{2} 
Step 2 : Find 0 Equivalent set. In this, we need to separate the nonfinal states from the final states.
[ q_{0 }q_{1} q_{2} q_{3} ] [q_{4}]
Step 3 : Find the 1Equivalent set. First, we consider [q_{0} q_{1}].(q_{0} q_{1}) go to state q_{1 }after transition on a and go to states q_{2 }and q_{3} after transition on b. Since q_{2} and q_{3 }belong to the same set of final states, therefore, [ q_{0 }q_{1 }] are equivalent.
Next, take [q_{0 }q_{2}].(q_{0 }q_{2}) go to q_{1} after transition on a and q_{2} after transition on b.
Therefore, [q_{0} q_{2}] are also equivalent.
Next, take [q_{0} q_{3}] . (q_{0} q_{3}) go to q_{1} after transition on a and q_{2} and q_{4} are transition on b. Therefore, [q_{0} q_{3}] are not equivalent since q_{2 }and q_{4} belong to the different set of final states.
Therefore, the 1equivalent will consist of: [q_{0}, q_{1}, q_{2}] [q_{3}] [q_{4}]
must read : Experts Tips to Solve NPComplete Problems in GATE 2017
Step 4 : Find the 2Equivalent .First, we check [q_{0} q_{1}]. (q_{0} q_{1}) go to q_{1} after transition on a and go to q_{2} and q_{3 }after transition on b.
Since, q2 and q3 belong to the different set of final states, Therefore, [q0 q1] are not equivalent. Next, we check [q_{0} q_{2}].
(q_{0} q_{2}) go to q_{1} after transition on a and q_{2 }after transition on b. Therefore, [q_{0} q_{2}] are equivalent.
Therefore, 2equivalent would be [q_{0} ,q_{2}] [q_{1}] [q_{3}] [q_{4}] .
Step 5 :
Finding further equivalent would result in the same set of states. Therefore, the minimized DFA would be
In this, [q_{0} q_{2}] would be taken as a single state since these two are equivalent. Finally, we obtain the following minimized DFA.
Best Wishes !!