Canonical forms for information-lossless finite-state logical machines

Abstract

An important class of finite-state machines transforms input sequences of digits into output sequences in a way such that, after an experiment of any finite length on the machine, its input sequence may be deduced from a knowledge of the corresponding output sequence, its initial and final states, and the set of specifications for the transformations by which the machine produces output sequences from input sequences. These machines are called "information-lossless." Canonical circuit forms are shown into which any information-lossless machines may be synthesized. The existence of inverses for these circuits is investigated and circuits for their realization are derived.