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 .
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 (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 is in one class because both are final state (zero length string λ only accepted by final state) and is in one class because they are non-final state and not accepted at zero length string λ.
Here is in one class because for one length input string 0 or 1 both contain final state (see transition function table).
For belong to a single class because for one length input string 0 or 1 both contain non-final state (see transition function table).
For 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 , then we have to check the behavior for 00, 01, 10, 11
But if we start with from (already checked for single input variables), then we only need to check for next single string 0, 1 at . Now put 0 and 1 at and create new class .
If we again check behavior for next length then it must be same.
So we can say if then so we stop checking behavior for equivalent class, if we got .
Step 4: Now we merge the same equivalent classes (states) so, we merge and
Here we can replace by or by , same we can replace by or by .
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 and also , at we get all the states atomic.