On the Bound to the Memory of a Sequential Machine

Following Moore [1], consider a sequential machine (discrete, synchronius automata) having n states or less, m inputs, and p-possible outputs. The state that the machine is in at a given time depends only on the state at the previous time and the previous input. The output at a given time depends only on the current state. In addition the machine is strongly connected. That is to say, it is possible to take it from any state to any other state by means of some sequence of inputs. Finally, the machine is in reduced form, which may be taken to mean that it is not possible to design a sequential machine having fewer states whose behavior, in so far as its inputs and outputs are concerned, is identical with the behavior of the original machine. As a gedanken experiment, one may attempt to determine the table of state transitions and outputs of this machine (to within a renaming of its states) by applying inputs and observing the corresponding outputs. It is assumed that one does not just open up the machine and trace its circuits. What will be the length of this gedanken experiment? That is, how many inputs are needed?