states of some dfa M, then the graph associated with M will have one vertex
labeled q 0 and another labeled q 1 . An edge (q 0 ,q 1 ) labeled a represents the
transition δ(q 0 ,a) = q 1 . The initial state will be identified by an incoming
unlabeled arrow not originating at any vertex. Final states are drawn with a
double circle.
More formally, if M = (Q, Σ,δ,q 0 ,F) is a deterministic finite accepter, then its
associated transition graph G M has exactly |Q| vertices, each one labeled with a
different q i ∈ Q. For every transition rule δ (q i ,a) = q j , the graph has an edge
(q i ,q j ) labeled a. The vertex associated with q 0 is called the initial vertex, while
those labeled with q f ∈ F are the final vertices. It is a trivial matter to convert
from the (Q, Σ,δ,q 0 ,F) definition of a dfa to its transition graph representation
and vice versa.
Example 2.1
The graph in Figure 2.1 represents the dfa
M =({q 0 ,q 1 ,q 2 },{0, 1},δ,q 0 ,{q l }),
where δ is given by
This dfa accepts the string 01. Starting in state q 0 , the symbol 0 is read first.
Looking at the edges of the graph, we see that the automaton remains in state q 0 .
Next, the 1 is read and the automaton goes into state q 1 . We are now at the end of
the string and, at the same time, in a final state q 1 . Therefore, the string 01 is
accepted. The dfa does not accept the string 00, since after reading two
consecutive 0’s, it will be in state q 0 . By similar reasoning, we see that the
automaton will accept the strings 101, 0111, and11001, but not 100 or 1100.
Figure 2.1