Inference of State Machines from Examples of Behavior

Often, the desired behavior of a system is known before a design of the system is known. It usually falls to the designer to correctly translate this behavior into a system that exhibits it. This report describes two algorithms that design systems guaranteed to exhibit specified behavior. Specifically, our algorithms identify a state machine with the fewest states exhibiting behavior specified by a set of input/output strings. One algorithm builds the machine explicitly by fitting together transitions that correspond to input/output pairs. The other implicitly considers all machines of a given size and discards those not exhibiting the desired behavior. Although the problem is NP-complete, our algorithms behave exponentially only in the number of states in the minimum machine; other state-minimization algorithms behave exponentially in the size of the behavior specification. This advantage has allowed machines of up to fourteen states to be identified exactly within an hour. Contents..