Section 9.3 Finite-State Machines
739
Minimization Procedure
Assuming now that all unreachable states have been removed from M, we will
continue to look for a reduced machine M′. The key to finding a reduced M′, if
one exists, lies in the notion of equivalent states.
Definition EquivALEnt stAtEs
Two states s i and s j of M are equivalent if for any a [ I*, f O (s i , a) = f O (s j , a),
where I* again denotes the set of finite-length strings over the input alphabet.
In this definition of equivalent states, the definition of the output function has
been extended to denote the sequence of output symbols obtained by repeatedly
applying f O to a sequence a of input symbols. Thus equivalent states of a machine
produce identical output strings for any input string.
PrACtiCe 53 Prove that state equivalence is an equivalence relation on the states of a machine.
■
For the time being, we will postpone the problem of how to identify equivalent
states in a given machine M. Let’s simply assume that we have somehow found
which states are equivalent and have partitioned the states of M into the corresponding equivalence classes. These classes have two properties: (1) All states in the same
class have the same output, and (2) for each input symbol, all states in the same class
proceed under the next-state function to states that are all in the same class.
PrACtiCe 54 Show that properties 1 and 2 are satisfied when M is partitioned into classes of equivalent
states.
■
We define a machine M′ whose states are the equivalence classes of M. M′ has
the same input and output alphabet as M, and its start state is the class to which
s 0 , the start state of M, belongs. The output of a class is the output symbol common to all states of M in that class (property 1). The next state of class X under
an input symbol is that class to which all states of M in X proceed under that
input symbol (property 2). M′ is a well-defined machine. M′ produces the same
output strings when processing a given input string as does M. Also, the number
of states of M′ (equivalence classes of M) will be no greater than the number of
states of M.
The minimization problem for M thus boils down to finding the equivalent
states of M. Perhaps we should note first that the obvious approach of directly trying to satisfy the definition of equivalent states will not work. Given two states s i
and s j of M, we cannot actually compare the outputs corresponding to each possible input string. Fortunately, the problem is not as infinite as it sounds; we only
need to identify k-equivalent states.
Definition K-EquivALEnt stAtEs
Two states s i and s j of M are k-equivalent if for any a [ I* where a has no more
than k symbols, f O (s i , a) = f O (s j , a).
739
Minimization Procedure
Assuming now that all unreachable states have been removed from M, we will
continue to look for a reduced machine M′. The key to finding a reduced M′, if
one exists, lies in the notion of equivalent states.
Definition EquivALEnt stAtEs
Two states s i and s j of M are equivalent if for any a [ I*, f O (s i , a) = f O (s j , a),
where I* again denotes the set of finite-length strings over the input alphabet.
In this definition of equivalent states, the definition of the output function has
been extended to denote the sequence of output symbols obtained by repeatedly
applying f O to a sequence a of input symbols. Thus equivalent states of a machine
produce identical output strings for any input string.
PrACtiCe 53 Prove that state equivalence is an equivalence relation on the states of a machine.
■
For the time being, we will postpone the problem of how to identify equivalent
states in a given machine M. Let’s simply assume that we have somehow found
which states are equivalent and have partitioned the states of M into the corresponding equivalence classes. These classes have two properties: (1) All states in the same
class have the same output, and (2) for each input symbol, all states in the same class
proceed under the next-state function to states that are all in the same class.
PrACtiCe 54 Show that properties 1 and 2 are satisfied when M is partitioned into classes of equivalent
states.
■
We define a machine M′ whose states are the equivalence classes of M. M′ has
the same input and output alphabet as M, and its start state is the class to which
s 0 , the start state of M, belongs. The output of a class is the output symbol common to all states of M in that class (property 1). The next state of class X under
an input symbol is that class to which all states of M in X proceed under that
input symbol (property 2). M′ is a well-defined machine. M′ produces the same
output strings when processing a given input string as does M. Also, the number
of states of M′ (equivalence classes of M) will be no greater than the number of
states of M.
The minimization problem for M thus boils down to finding the equivalent
states of M. Perhaps we should note first that the obvious approach of directly trying to satisfy the definition of equivalent states will not work. Given two states s i
and s j of M, we cannot actually compare the outputs corresponding to each possible input string. Fortunately, the problem is not as infinite as it sounds; we only
need to identify k-equivalent states.
Definition K-EquivALEnt stAtEs
Two states s i and s j of M are k-equivalent if for any a [ I* where a has no more
than k symbols, f O (s i , a) = f O (s j , a).