Automata for learning sequential tasks

This paper describes a system that is capable of learning both combinational and sequential tasks. The system learns from sequences of input/output examples in which each pair of input and output represents a step in a task. The system uses finite state machines as its internal models. This paper proposes a method for inferring finite state machines from examples. New algorithms are developed for modifying the finite state machines to allow the system to adapt to changes. In addition, new algorithms are developed to allow the system to handle inconsistent information that may result from noise in the training examples. The system can handle sequential tasks involving long-term dependencies for which recurrent neural networks have been shown to be inadequate. Moreover, the learned finite state machines are easy to be implemented in VLSI. The system has a wide range of applications including but not limited to (a) sequence detection, prediction, and production, (b) intelligent macro systems that can learn rather than simply record sequences of steps performed by a computer user, and (c) design automation systems for designing finite state machines or sequential circuits.