Minimization Of DFA| Theory Of Computation


Theory And Numerical

Theory:

Minimization of DFA is required to obtain the minimal version of any DFA which consists of the minimum number of states possible.
suppose you designed a DFA with 5 states and your friend designed it with 4 states, so both are correct but the DFA with less number of states will be more efficient. So the DFA designed by your friend will be more efficient.
So now how can you make your DFA to 4 states? What you'll do here is that you'll combine 2states such that both the states are equivalent.
When are two states said to be equivalent?
Two states 'A'and 'B'are said to be equivalent if
Minimization Of Dfa
Where 'X' is any input String.
Types of equivalences:
If |X|=0, then A and B are said to be 0 equivalent
If |X|=1, then A and B are said to be 1 equivalent
If |X|=2, then A and B are said to be 2 equivalent
.
.
.
.
If |X|=n, then A and B are said to be n equivalent.

Rules for the minimization of DFA:


i) Final state can be replaced by final state only.
ii) Non-Final can be replaced by non final state.
iii) Initial state can not be replaced by any other state.
iv) Non-final state can't be replaced by final state & vice versa.

Example:

We have to minimize this DFA into lesser states

dfa

Here q0 is the initial state and q4 is the final state.

So, now firstly we'll make a transition table for the given DFA.

transition table

Now let's find the equivalents.

0 equivalent: {q0,q1,q2,q3} {q4}

Here we have separated the final and non-final states into sets.

1 equivalents: Now check the pairs of non-finals states for 0 and 1 in the transition table if the values are same then its ok but if the values are different then check if the values are in the set of non-final state or not, if the values are in set then keep as it is, these states are equivalent to each other. And check for all the pairs but if both the values are not in the non-final state set then separate the state for which the values are not in set.

{q0,q1,q2} {q3} {q4}

q3 got seperated as, q0, q1 are equivalent q2, q0 is equivalent but q3 is not equivalent to any state.

Similarly, for 2 equivalent: {q0 ,q2} {q1} {q3} {q4}

Now for 3 to any equivalents the sets will be same so we don't need to find anymore equivalents.

So, now the 5 state DFA is converted into 4 state DFA with states {q0,q2}, {q1}, {q3}, {q4}.

Custom Search

%d bloggers like this: