O
Chapter 2
Finite
Automata
ur introduction in the first chapter to the basic concepts of
computation, particularly the discussion of automata, is brief and
informal. At this point, we have only a general understanding of what
an automaton is and how it can be represented by a graph. To
progress, we must be more precise, provide formal definitions, and
start to develop rigorous results. We begin with finite accepters, which are a
simple, special case of the general scheme introduced in the last chapter. This
type of automaton is characterized by having no temporary storage. Since an
input file cannot be rewritten, a finite automaton is severely limited in its
capacity to “remember” things during the computation. A finite amount of
information can be retained in the control unit by placing the unit into a specific
state. But since the number of such states is finite, a finite automaton can only
deal with situations in which the information to be stored at any time is strictly
bounded. The automaton in Example 1.16 is an instance of a finite accepter.
2.1 Deterministic Finite Accepters
The first type of automaton we study in detail are finite accepters that are
deterministic in their operation. We start with a precise formal definition of
deterministic accepters.
Deterministic Accepters and Transition Graphs
In common with all automata, a deterministic accepter has internal states, rules
for transitions from one state to another, some input, and ways of making