Experiments with finite state machines

The purpose of this study is to introduce and illustrate the various types of experiments with finite state machines. A finite state machine is an abstract object composed of a finite number of input, output and state symbols. The behavior of the machine is described by a functional relationship between input, output and state. In designing a finite state machine it often happens that two states represent the same internal condition. Therefore it is desirable to develop a technique for transforming one machine into another which has no redundant states, so that both have the same behavior. The definition of k-equivalent and k-distinguishable are useful in an algorithm which is developed to determine which states of the machine are equivalent. The machine with no two equivalent states is a reduced machine. An experiment on a reduced state machine consists of applying an input sequence and observing the output. The classification of experiments is (1) simple and multiple experiments; (2) preset and adaptive experiments; (3) distinguishing and homing experiments. The successor tree is a useful device in designing the experiment. The successor tree is terminated by specific rules in each experiment. Homing and distinguishing experiments can be either preset and adaptive. All reduced machines have a homing sequence. A distinguishing sequence is sometimes possible in both preset and adaptive form. However, some reduced machines have only an adaptive experiment and some do not have any simple distinguishing sequence at all