###
1 Algorithm to Detect Unreachable States

Input *M* = (*Q*, Σ, δ, *q*_{0}, *F* )

Output = Set *U* (which is set of unreachable states)

{Let *R* be the set of reachable states of DFA. We take two *R*'s, *R*_{new}, and *R*_{old} so that we will be able to perform iterations in the process of detecting unreachable states.}

begin

*R*_{old} = φ
*R*_{new} = {q_{0}}

while (*R*_{old} # *R*_{new}) do

begin

temp_{1} = *R*_{new} − *R*_{old}
*R*_{old} = *R*_{new}
temp_{2} = φ
for every *a* in Σ do

temp_{2} = temp_{2} ∪ δ( temp_{1}, *a*)

*R*_{new} = *R*_{new} ∪ temp_{2}
end
*U* = *Q* − *R*_{new}
end

If *p* and *q* are the two states of a DFA, then *p* and *q* are said to be ‘distinguishable’ states if a distinguishing string *w* exists that distinguishes *p* and *q*.

A string *w* is a distinguishing string for states *p* and *q* if transitions from *p* on *w* go to a nonfinal state, whereas transitions from *q* on *w* go to a final state, or vice versa.

Therefore, to find nondistinguishable states of a DFA, we must find out whether some distinguishing string *w*, which distinguishes the states, exists. If no such string exists, then the states are nondistinguishable and can be merged together.

The technique that we use to find nondistinguishable states is the method of successive partitioning. We start with two groups/partitions: one contains all nonfinal states, and other contains all the final state. This is because if every final state is known to be distinguishable from a nonfinal state, then we find transitions from members of a partition on every input symbol. If on a particular input symbol *a* we find that transitions from some of the members of a partition goes to one place, whereas transitions from other members of a partition go to an other place, then we conclude that the members whose transitions go to one place are distinguishable from members whose transitions goes to another place. Therefore, we divide the partition in two; and we continue this partitioning until we get partitions that cannot be partitioned further. This happens when either a partition contains only one state, or when a partition contains more than one state, but they are not distinguishable from one another. If we get such a partition, we merge all of the states of this partition into a single state. For example, consider the transition diagram in Figure 1.

Initially, we have two groups, as shown below:

Since

Partitioning of Group I is not possible, because the transitions from all the members of Group I go only to Group I. But since

state *F* is distinguishable from the rest of the members of Group I. Hence, we divide Group I into two groups: one containing *A*, *B*, *C*, *E*, and the other containing *F*, as shown below:

Since

partitioning of Group I is not possible, because the transitions from all the members of Group I go only to Group I. But since

states *A* and *E* are distinguishable from states *B* and *C*. Hence, we further divide Group I into two groups: one containing *A* and *E*, and the other containing *B* and *C*, as shown below:

Since

state *A* is distinguishable from state *E*. Hence, we divide Group I into two groups: one containing *A* and the other containing *E*, as shown below:

Since

partitioning of Group III is not possible, because the transitions from all the members of Group III on *a* go to group III only. Similarly,

partitioning of Group III is not possible, because the transitions from all the members of Group III on *b* also only go to Group III.

Hence, *B* and *C* are nondistinguishable states; therefore, we merge *B* and *C* to form a single state, *B*_{1}, as shown in Figure 2.