ON THE SYNTHESIS OF FINITE-STATE MACHINES FROM SAMPLES OF THEIR BEHAVIOR

Techniques have been given for machine synthesis from input-output behavior by Gill [7], Ginsburg [8], [9], Gray Nerode [15] has given a method for synthesizing finitestate and Harrison [11], Tal [17], and others. Each of these machines from their associated right-invariant equivalence methods requires that enough information be included in relations. In this note, we introduce a modification of the problem statement so that the solution is unique, and the Nerode relation and show how it can be used to synthesize in contrast to the method presented here, they do not have a machines from finite subsets of their behavior. The capability to utilize unspecified or DON'T CARE conditions to technique described is a method for finding a nondeterministic produce simpler solutions. The method described here yields machine that realizes a given finite set of input - machines that satisfy the known input-output requirements output pairs, and it includes a parameter k that allows one and that often given "reasonable" behavior outside of the to vary the precision and complexity of the synthesized machine.