be removed (along with all transitions relating to it) without affecting the
language accepted by the automaton. But even after the removal of q 5 , the first
automaton has some redundant parts. The states reachable subsequent to the first
move δ (q 0 ,0) mirror those reachable from a first move δ (q 0 ,1). The second
automaton combines these two options.
Figure 2.17
From a strictly theoretical point of view, there is little reason for preferring
the automaton in Figure 2.17(b) over that in Figure 2.17(a). However, in terms of
simplicity, the second alternative is clearly preferable. Representation of an
automaton for the purpose of computation requires space proportional to the
number of states. For storage efficiency, it is desirable to reduce the number of
states as far as possible. We now describe an algorithm that accomplishes this.
Definition 2.8
Two states p and q of a dfa are called indistinguishable if
and
language accepted by the automaton. But even after the removal of q 5 , the first
automaton has some redundant parts. The states reachable subsequent to the first
move δ (q 0 ,0) mirror those reachable from a first move δ (q 0 ,1). The second
automaton combines these two options.
Figure 2.17
From a strictly theoretical point of view, there is little reason for preferring
the automaton in Figure 2.17(b) over that in Figure 2.17(a). However, in terms of
simplicity, the second alternative is clearly preferable. Representation of an
automaton for the purpose of computation requires space proportional to the
number of states. For storage efficiency, it is desirable to reduce the number of
states as far as possible. We now describe an algorithm that accomplishes this.
Definition 2.8
Two states p and q of a dfa are called indistinguishable if
and