The Structure and Behavior of Finite Automata

At the beginning of chapter 2 we proposed that finite k-algebra is one way of interpreting the intuitive idea of deterministic sequential system, as described in the introduction. In fact, it is clear how k-algebras make precise such ideas as input channel and internal configuration; a finite k-algebra (given by a table, transition graph, or transition tree) fully describes the internal response, to input stimuli, of a deterministic sequential system. However, we are left to make provisions for output of stimuli from the system to the environment. This is the subject of the present chapter, where we will introduce outputs g of a finite k-algebra A, to complete the rigorous definition of deterministic sequential systems. The resulting systems are called finite automata. We will study their structure and oppose this idea to that of behavior. The black-box behavior (or input-to-output behavior) tells how the system translates input stimuli to output stimuli and can be tested even when we have no access to the internal structure of the system. In contrast, the box will have to be worked on (with a screw driver or a can opener) if it is to reveal its structure .