Memory-span concepts and the synthesis of sequential machines in feedback shift-register form

Various procedures have long been known for synthesizing a sequential machine with a feedback shift-register if each state is to have exactly one assignment; however, these approaches fail if each state is allowed to have more than one assignment. Herein lies the equivalent-state problem. The equivalent-state problem is approached by establishing a relationship between feedback shift-register realizable flow tables and finite memory-span. From this relationship, a necessary and sufficient condition is derived for the realizability of a sequential machine with a feedback shift-register. The concept of the pair-graph is introduced which is used to bound the level and length of the feedback shift-register realization of a sequential machine. From an investigation of the pair-graph, recursive procedures arise which test sequential machines in which each state has L distinct successors for L-level feedback shift-register realizability. The complexity of feedback shift-register synthesis of more general machines is demonstrated.