Minimization of DFA



Transition function table from the above machine



Follow the steps to minimize the DFA


Step1: Remove the states which are not reachable from starting state. Example: here (q5).


Step2: After that we write transition function.


Step3: Now we are going to minimize it. First we find out equivalent class (those classes whose state behavior is same). So, first we calculate π0  (zero length string behavior (accepted or rejected), zero length string λ).


If we put λ at final state, then it will be accepted, but if we put λ at non final state, then it will be rejected.


Now we find out equivalent classes. One category set of states accepted by λ, second category set of states not accepted by λ.



Here {q3, q4} is in one class because both are final state (zero length string λ only accepted by final state) and {q0, q1, q2} is in one class because they are non-final state and not accepted at zero length string λ. 


For one length string behavior


Here {q3, q4} is in one class because for one length input string 0 or 1 both contain final state (see transition function table).


For {q0}  belong to a single class because for one length input string 0 or 1 both contain non-final state (see transition function table).


For {q1, q2}  is in one class because for one length input string 0 or 1, it contain final state for input 1 and non-final state for input 0 (see transition function table).



If we start with from π0 , then we have to check the behavior for 00, 01, 10, 11


But if we start with from π1  (already checked for single input variables), then we only need to check for next single string 0, 1 at π1{{q3, q4}, {q0}, {q1, q2}} .  Now put 0 and 1 at π1 and create new class π2.



But here π1 = π2  


If we again check behavior for next length  then it must be same.


So we can say if π1 = π2  then π2 = π3 = π4 = π5 ....... so we stop checking behavior for equivalent class, if we got πk = πk + 1.


Step 4: Now we merge the same equivalent classes (states) so, we merge {q3, q4} and {q1, q2}


Here we can replace q3by q4 or q4by q3 , same we can replace q1by q2  or q2by q1.



Step5:  Now we remove repeated state and form final transition function table:



Step 6:  Design minimized DFA from final transition function table:



RE = (0 + 1)0*1(0 + 1)* 


If we want to do minimize the already minimized DFA then we never get a merge states, it look like {q0}  {q1}  {q2}  {q3}  {q4} and also πk = πk + 1 = πn , at πn we get all the states atomic.