During the transition from one time interval to the next, output may be produced
or the information in the temporary storage changed. The term configuration
will be used to refer to a particular state of the control unit, input file, and
temporary storage. The transition of the automaton from one configuration to the
next will be called a move.
Figure 1.4
This general model covers all the automata we will discuss in this book. A
finite-state control will be common to all specific cases, but differences will arise
from the way in which the output can be produced and the nature of the
temporary storage. As we will see, the nature of the temporary storage governs
the power of different types of automata.
For subsequent discussions, it will be necessary to distinguish between
deterministic automata and nondeterministic automata. A deterministic
automaton is one in which each move is uniquely determined by the current
configuration. If we know the internal state, the input, and the contents of the
temporary storage, we can predict the future behavior of the automaton exactly.
In a nondeterministic automaton, this is not so. At each point, a nondeterministic
automaton may have several possible moves, so we can only predict a set of
possible actions. The relation between deterministic and nondeterministic
automata of various types will play a significant role in our study.
An automaton whose output response is limited to a simple “yes” or “no” is
called an accepter. Presented with an input string, an accepter either accepts the
string or rejects it. A more general automaton, capable of producing strings of
symbols as output, is called a transducer.