Problem Solving in Automata, Languages, and Complexity

Finite Automata

2.1 Deterministic Finite Automata

In this section, we introduce a simple machine model, called deterministic
finite automata, that will be shown later to recognize exactly the class of
regular languages. Intuitively, a deterministic finite automaton (DFA) is a
simple machine which reads an input string one letter at a time and then,
after the input is completely read, decides to accept or to reject the input.
A DFA consists of three parts: a tape, a tape head (or, simply, head), and a
finite control.
The tape is used to store the input data. It is divided into a finite number
of cells. Each cell holds a symbol from a given alphabet C. The tape head
scans the tape, reads symbols from the tape, and passes the information to
the finite control. At each move of the DFA, the head scans one cell of the
tape and reads the symbol in the cell, and then moves to the next cell to the
right.
The finite control has a finite number of states which form the state set
Q. At the beginning of a move, the control is in one of the states. Then,
it determines, from the current state and the symbol read by the tape head,
how the state is changed to a new state. More precisely, the change of state
at each move is governed by a state trunsition function (or, simply, transition
function) S : Q x C + Q. At each move, if the finite control is currently at
state q E Q and the symbol read by the tape head is a E C, then the finite
control changes to the new state p = 6(q, a>.
To complete the description of a DFA, we need to specify two special kinds
23

Problem Solving in Automata, Languages, and Complexity.

Ding-Zhu Du, Ker-I Ko

Copyright2001 by John Wiley & Sons, Inc.

ISBNs: 0-471-43960-6 (Hardback); 0-471-22464-2 (Electronic)