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

Abstract

Let M be an incompletely specified aequential 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, anc in particular. sufficient conditions are given for which the state minimization problems for M and A' 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 5' ⊂ S. such that if S is an element of a C-class Σ for M, then (Σ - {S}) {S'} is a C-clus for M. Using these results, which restrict the family of C -classes one needs to consider, algorithms are described for two state -minimization problems.