An Efficient Algorithm which Determines the Output from a Sequential Machine for Regular Inputs
Kenneth B. Salomon · The Computer Journal · 1974
This paper deals with the following problem from automata theory: given a deterministic sequential machine, calculate its set of outputs when a given regular set is used as input. The output is known to be regular and various effective methods have been developed in the past to determine it. However these methods tend to be quite inefficient and ill-suited to either hand or computer calculation. The procedure developed here is sufficiently efficient and straightforward as to be suitable for machine implementation and, in fact, makes use of an already-existing SNOBOL IV program.