FOR FREE YEAR SOLVED

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 $\mathbf{\left(}{\mathit{q}}_{\mathbf{5}}\mathbf{\right)}$.

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 ${\mathbf{\pi }}_{\mathbf{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 $\mathbf{\{}{\mathit{q}}_{\mathbf{3}}\mathbf{,}\mathbf{ }{\mathit{q}}_{\mathbf{4}}\mathbf{\}}$ is in one class because both are final state (zero length string λ only accepted by final state) and $\mathbf{\{}{\mathit{q}}_{\mathbf{0}}\mathbf{,}\mathbf{ }{\mathit{q}}_{\mathbf{1}}\mathbf{,}\mathbf{ }{\mathit{q}}_{\mathbf{2}}\mathbf{\}}$ is in one class because they are non-final state and not accepted at zero length string λ. 

Here $\mathbf{\{}{\mathit{q}}_{\mathbf{3}}\mathbf{,}\mathbf{ }{\mathit{q}}_{\mathbf{4}}\mathbf{\}}$ is in one class because for one length input string 0 or 1 both contain final state (see transition function table).

For $\mathbf{\left\{}{\mathit{q}}_{\mathbf{0}}\mathbf{\right\}}$  belong to a single class because for one length input string 0 or 1 both contain non-final state (see transition function table).

For $\mathbf{\{}{\mathit{q}}_{\mathbf{1}}\mathbf{,}\mathbf{ }{\mathit{q}}_{\mathbf{2}}\mathbf{\}}$  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 ${\mathbf{\pi }}_{\mathbf{0}}$ , then we have to check the behavior for 00, 01, 10, 11

But if we start with from ${\mathbf{\pi }}_{\mathbf{1}}$  (already checked for single input variables), then we only need to check for next single string 0, 1 at ${\mathbf{\pi }}_{\mathbf{1}}\mathbf{\left\{}\mathbf{\right\{}{\mathbf{q}}_{\mathbf{3}}\mathbf{,}\mathbf{ }{\mathbf{q}}_{\mathbf{4}}\mathbf{\}}\mathbf{,}\mathbf{ }\mathbf{\{}{\mathbf{q}}_{\mathbf{0}}\mathbf{\}}\mathbf{,}\mathbf{ }\mathbf{\{}{\mathbf{q}}_{\mathbf{1}}\mathbf{,}\mathbf{ }{\mathbf{q}}_{\mathbf{2}}\mathbf{\left\}}\mathbf{\right\}}$ .  Now put 0 and 1 at ${\mathbf{\pi }}_{\mathbf{1}}$ and create new class ${\mathbf{\pi }}_{\mathbf{2}}$.

But here ${\mathbf{\pi }}_{\mathbf{1}}\mathbf{ }\mathbf{=}\mathbf{ }{\mathbf{\pi }}_{\mathbf{2}}\mathbf{ }\mathbf{ }$

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

So we can say if ${\mathbf{\pi }}_{\mathbf{1}}\mathbf{ }\mathbf{=}\mathbf{ }{\mathbf{\pi }}_{\mathbf{2}}\mathbf{ }$ then ${\mathbf{\pi }}_{\mathbf{2}}\mathbf{ }\mathbf{=}\mathbf{ }{\mathbf{\pi }}_{\mathbf{3}}\mathbf{ }\mathbf{=}\mathbf{ }{\mathbf{\pi }}_{\mathbf{4}}\mathbf{ }\mathbf{=}\mathbf{ }{\mathbf{\pi }}_{\mathbf{5}}\mathbf{ }\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}$ so we stop checking behavior for equivalent class, if we got ${\mathbf{\pi }}_{\mathit{k}}\mathbf{ }\mathbf{=}\mathbf{ }{\mathbf{\pi }}_{\mathit{k}\mathbf{ }\mathbf{+}\mathbf{ }\mathbf{1}}$.

Step 4: Now we merge the same equivalent classes (states) so, we merge $\mathbf{\{}{\mathit{q}}_{\mathbf{3}}\mathbf{,}\mathbf{ }{\mathit{q}}_{\mathbf{4}}\mathbf{\}}$ and $\mathbf{\{}{\mathit{q}}_{\mathbf{1}}\mathbf{,}\mathbf{ }{\mathit{q}}_{\mathbf{2}}\mathbf{\}}$

Here we can replace ${\mathit{q}}_{\mathbf{3}}$by ${\mathit{q}}_{\mathbf{4}}$ or ${\mathit{q}}_{\mathbf{4}}$by ${\mathit{q}}_{\mathbf{3}}$ , same we can replace ${\mathit{q}}_{\mathbf{1}}$by ${\mathit{q}}_{\mathbf{2}}$  or ${\mathit{q}}_{\mathbf{2}}$by ${\mathit{q}}_{\mathbf{1}}$.

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 $\mathbf{\left\{}{\mathit{q}}_{\mathbf{0}}\mathbf{\right\}}\mathbf{ }\mathbf{ }\mathbf{\left\{}{\mathit{q}}_{\mathbf{1}}\mathbf{\right\}}\mathbf{ }\mathbf{ }\mathbf{\left\{}{\mathit{q}}_{\mathbf{2}}\mathbf{\right\}}\mathbf{ }\mathbf{ }\mathbf{\left\{}{\mathit{q}}_{\mathbf{3}}\mathbf{\right\}}\mathbf{ }\mathbf{ }\mathbf{\left\{}{\mathit{q}}_{\mathbf{4}}\mathbf{\right\}}$ and also ${\mathbf{\pi }}_{\mathit{k}}\mathbf{ }\mathbf{=}\mathbf{ }{\mathbf{\pi }}_{\mathit{k}\mathbf{ }\mathbf{+}\mathbf{ }\mathbf{1}}\mathbf{ }\mathbf{=}\mathbf{ }{\mathbf{\pi }}_{\mathbf{n}}$ , at ${\mathbf{\pi }}_{\mathit{n}}$ we get all the states atomic.