Problem Solving in Automata, Languages, and Complexity

24 FINKI- AUTOMATA

finite

Figure 2.1: A finite automaton.

of states: an initial stute 40 at which the DFA begins to work, and a set F C - Q
of final states at which the DFA certifies that the input is in the language.
Thus, a DFA can be represented as a quintuple M = (Q, C, S, 40, F).
How does a DFA A4 work exactly? Initially, the DFA A4 is in the initial
state, the tape holds the input string, and the tape head scans the leftmost
cell of the tape. Then, the DFA M operates, move by move, according to
the transition function 6. The DFA M halts after it reads the symbol in the
rightmost cell of the tape and its tape head moves off the tape. When the
DFA halts, it uccepts the input string if it halts in one of the final states.
Otherwise, the input string is rejected. The set of all strings accepted by a
DFA A& is denoted by L(M). W e a 1 so say that the language L(M) is accepted
by M.
The transition diagram of a DFA is an alternative way to represent the DFA.
For M = (Q,C,S,qo,F), th e t ransition diagram of M is a labeled digraph
(V, E) satisfying

V = Q,

where q -% p denotes an edge (q, p) with label a. In addition, the initial state
of the DFA is pointed to by an arrow without a starting vertex, and every
final state is denoted by double circles.

Example 2.1 Consider a DFA M = (Q, C,S, qo, F) where Q = {qo, ql, q2,

q3}, c = {O,l), F = +ll, 921, and 6 is the function defined by the following

table:

s 0 1

Qo 41 q3

T

Ql 42 !I3

42 q2 !I2

q3 !I3 cl3

Then, the transition diagram of M is as shown in Figure 2.2. (A number i in
a circle or in double circles denotes the state qi.) ’^0