Easily Testable Sequential Machines with Extra Inputs

In this paper, an easily testable machine is defined as one which possesses: 1) a distinguishing sequence of length log2n] which forces the machine into a specific state S1, and 2) transfer sequences of length at most [log2n] to carry the machine from state S1 to state Si for all i. A design procedure is presented in which an arbitrary machine is augmented to an easily testable machine by adding two special input symbols to the original machine. An efficient procedure is also described for designing checking experiments for the easily testable machines. For an n-state, m-input symbol machine, this procedure gives a bound on the length of the checking experiment that is approximately mn[log2n]. n]. Furthermore, the total checking experiments are preset.