Structure theory for the realization of finite state automata Progress report, 1 Nov. 1966 - 30 Apr. 1967
C. L. Coates · NASA Technical Reports Server (NASA)
The work initiated under t h i s grant during the first six month period f a l l s within two catagories.One is concerned with controlling the structure of synchronous realizations of finite state automata (sequential machines) when t h e storage elements of t h e machine are flip-flops.Basically t h i s is the problem of assigning binary c o d e s to the s t a t e , input and output alphabets in such a way a s to control the extent to which the flip-flop inputs depend upon the contents of the other flip-flop elements.The results are directed toward determining when realizations c a n b e fabricated b y networks of smaller machines.This not only reduces the number of components but allows some control of how the components are interconnected.The initial work (Ref. 1) on t h i s problem w a s completed prior to t h e initiation of this grant.gations have continued toward the objective of determining bow the feedback c a n be controlled when the storage elements a r e flip-flops.The r e s u l t s of t h i s study have not been completed but will be reported a t the end of the next period.During t h e period of t h i s report, investi-Related to the problem of controlling the structure by which machines a r e realized is the problem of controlling machine errors.In t h i s regard Hartmanis and Stearns (Ref. 2 , 3 and 4) defined t h e concept of inessential errors.Basically these a r e s t a t e errors within the machine that occur because of a temporary malfunction.Although they remain a s state errors they produce only a finite number of output errors even for infinitely long input sequences.Although Hartmanis and Stearns characterized inessential errors in terms of a state partition 5 , they did not provide a procedure for calculating t h i s partition.In fact, they showed t h a t it w a s not determined by state partitions with either the pair or the substitution property relations.During the current reporting period we have defined a procedure for determining inessential errors.~ An initial draft of the r e s u l t s of t h i s study is included in Part 11.The second category of investigations is concerned with asynchronous realizations of finite state automata that c o n s i s t of a combinational logic network with feedback.Included in t h i s study is the u s e of threshold logic gates. 1 4 The problems a s s o c i a t e d with asynchronous realizations a r e those of assigning state, input and output c o d e s such that hazard and race conditions within the realization are minimized.reporting period work w a s completed on t h e study of hazards in threshold logic and a means for obtaining realizations that are free of logic hazards.During the current The r e s u l t s of t h i s study is included i n Part 111.* Most s f the material of Reference [SI h a s been recently published in the following book.Introduction t o the Theory of Switching Circuits, McGraw-Hill Book Co. , 284-306, 1965.(X+Z)(Y+Z)(X'+Y) # (X+Z)(X'+Y)