The document Minimization of DFA Computer Science Engineering (CSE) Notes | EduRev is a part of the Computer Science Engineering (CSE) Course Theory of Computation.

All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)

**Part IV. Minimization of DFA**

For a given language, many DFAs may exist that accept it. The DFA we produce from an NFA may contain many dead states, inaccessible states and indistinguishable states. all these unnecessary states can be eliminated from a DFA through a process called minimization. For practical applications, it is desirable that number of states in the DFA is minimum.

The algorithm for minimising a DFA is as follows:

Step 1: Eliminate any state that cannot be reached from the start state.

Step 2: Partition the remaining states into blocks so that all states in the same block are equivalent, and no pair of

states from different blocks are equivalent.

The process is demonstrated using an example:**Example 1:**

Minimise the following DFA,

Step 1: Eliminate any state that cannot be reached from the start state.

This is done by enumerating all the simple paths in the graph of the DFA beginning from the start state. Any state that is not part of some path is unreachable. In the above, the state q_{3} cannot be reached. So remove the corresponding to q_{3} from the transition table.

Now the new transition table is,

Step 2:

Divide the rows of the transition table into 2 sets as,

1. One set containing only those rows which starts from non-final states.

Set 1

2. Another set containing those rows which start from final states.

Set 2

Step 3a. Consider Set 1.

Find out the similar rows:

Row 2 and Row 6 are similar, since q_{1} and q_{7} transit to same states on inputs a and b. So remove one of them (for instance, q_{7}) and replace q_{7} with q_{1} in the rest.

We get,

Set 1

Now Row 1 and Row 3 are similar. So remove one of them (for instance, q_{4}) and replace q_{4} with q_{0} in the rest.

We get,

Set 1

Now there are no more similar rows.

Step 3b.

Consider Set 2,

Set 2

Do the same process for Set 2.

But it contains only one row. It is already minimized.

Step 4:

Combine Set 1 and Set 2

We get,

The DFA corresponding to this is,

Now this is a minimised DFA.

Transition diagram is,**Example 2:**

Minimise the following DFA,

Step 1: Eliminate any state that cannot be reached from the start state.

This is done by enumerating all the simple paths in the graph of the DFA beginning from the start state. Any state that is not part of some path is unreachable. In the above, the states q_{2} and q_{4} cannot be reached. So remove the rows corresponding to q_{2} and q_{4} from the transition

table.

We get,

Step 2: Divide the rows of the transition table into 2 sets as,

1. One set containing only those rows which starts from non-final states.

2. Another set containing those rows which start from final states.

Step 3a. Consider Set 1.

Find out the similar rows:

Set 1

There are no similar rows.

Step 3b. Consider Set 2.

Find out the similar rows:

Row 1 and Row 2 are similar, since q_{3} and q_{5} transit to same states on inputs 0 and 1.

So remove one of them (for instance, q_{5}) and replace q_{5} with q_{3} in the rest.

We get,

Step 4:

Combine Set 1 and Set 2

We get,

The DFA corresponding to this is,

Now this is a minimised DFA.

Transition diagram is,**Exercise:**

1. Minimise the following DFA represnted as transition table,

2. Minimise the following DFA represnted as transition table,

4. Minimise the following DFA represnted as transition table,

5. Minimise the following DFA represnted as transition table,

7. Minimise the following DFA represnted as transition table,

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!

18 videos|43 docs|39 tests