Minimization of DFA Multiple Final States Example

For Complete YouTube Video: Click Here

In this class, We discuss the Minimization of DFA Multiple Final States Example.

The reader should have prior knowledge of the minimization of DFA example. Click Here.

Consider the below DFA.

The first step, We need to remove the states that are not reachable from the initial state.

In our DFA, we have state q5, which is not reachable.

We need to remove the transitions on state q5.

The below diagram shows the DFA after removing the state q5.

Now we need to separate final and nonfinal states.

The states q0, q1, and q2 are nonfinal states and are named as set Q1.

The states q3 and q4 are final. and named as set Q2.

We do not have sets with a single state. So check for the division of both sets.

Point to remember: We need to divide the set Q1. So compare states present in set Q1.

Similarly, we need to divide set Q2. So compare the states present in set Q2.

The below table shows the transition table of the DFA.

Column four gives the transition of states to sets.

On state q0, if we apply input symbol a, we move to state q1. The state q1 is in the set Q1.

Similarly, we write for all the transitions.

From the fourth column, we observe, the state q1 and q2 are moving to the same sets.

The state q0 is not moving to the different sets. We divide the set Q1.

The states q3 and q4 are moving to the same sets. So no need to divide.

Now rename the sets.

The state q0 is one set and named Q1.

The state q1 and q2 in one set and named Q2.

the state q3 and q4 are in one set and named Q3.

Again find the transition movement on sets.

The fifth column gives the complete details.

From the fifth column, we can observe the sets are repeating. So we stop the process.

Combine the states q1 and q2. and the states q3 and q4 because they are moving to the same sets.

The below diagram shows the minimized transition diagram.