Some theorems for incompletely specified sequential machines with applications to state minimization

Let M be an incompletely specified sequential machine and Q be the set of internal states of M. We derive certain properties for classes of subsets of Q with particular emphasis on certain classes of compatible sets of states, subsequently called C-classes for M. We then briefly describe state minimization algorithms using these properties. The following types of theorems are proved: From an arbitrary incomplete machine M a machine M* is constructed which is transition complete, i.e., has a transition defined for every state and every input. Given a special type of partition of Q we construct from M a machine M\´ whose states correspond to the members of the partition. Relations between the C-classes of M and M\´ are given, and in particular, sufficient conditions are given for which the state minimization problems for M and M\´ are equivalent. Through the use of a class of sets of states "generated" by a given set of states of M, and a restricted type of compatibility relation between sets of states, certain sets of compatible states are shown not to be elements of any minimum C-class for M. Conditions are given on compatible sets S and S\´ of Q, where S\´ S/supseteq$S, such that if S is an element of a C-class Sigma for M, then (Sigma- {S}) $cup$ {S\´} is a C-class for M. Using these results, which restrict the family of C-classes one needs to consider, algorithms are described for two state-minimization problems.