2.1 Deterministic Finite Automata 25
Figure 2.2: The transition diagram of the DFA of Example 2.1.
Since the transition function S is well-defined on & x C, the transition
diagram of the DFA has the property that for every vertex (state) Q and
every symbol a, there exists exacly one edge with label a leaving Q. This
implies that for each string X, there exists exactly one path starting from ~0
whose labels form the string X. This path is called the computation path of
the DFA on ~xf. We note that a string x is accepted by M if and only if its
computation path ends at one of the final states.
To formally define the notion of a DFA accepting an input string, we extend
the transition function S from the domain Q x C to the domain Q x C by
the following inductive definition:
(1) &I, 4 = CL
(2) For any z E C and a E C, S(Q,za) = s(s(4,~),u).
With this extension, for any string x:, 6(qo, 2) is the last state in the compu-
tation path of the string X. Therefore, we can formally define that x E L(M)
if and only if S(qo, z) E F; that is,
L(M) = {z E c* 1 qqo,g E F).
Example 2.2 Consider the DFA M given by Figure 2.2. Determine whether
M accepts strings 000 and 010.
Solution. The computation path of the string 000 is the sequence qo, S(q0, 0) =
ql, 6(ql,O) = q2, and S(a2,O) = 42. Thus, S(qo,OOO) = q2 E F and M accepts- Similarly, we can find that S(qo, 010) = q3 4 F, and M rejects 010. 0
Example 2.3 What is the language L(M) accepted by the DFA M of Figure
2.2?Solution. We observe that once the DFA M enters state 43, it will never be
able to leave this state, and will reject the input string regardless what the
remaining part of the input string is. (We call such a state a failure state.)
On the other hand, once M enters state q2, it will never leave this state, and