28 FINITE AUTOMATA
0 a
0 C
Figure 2.6: Three DFA’s of Exercise 3.(b) Suppose n = 7, d = 2, a0 = 0 and al = 1. Find 6(qs,OlOl) and
S(ar, 11010).
(c) Suppose n = 7, d = 2, a0 = 0 and al = 1. Find binary strings CC
and y such that &-J, 2) = 45 and &-J, y) = q6.
*(d) Show that for any state qj E Q, there exists a string z E C* such
that S(qo, Z) = qj.- For each of the DFA’s A&, A.42 and A&, as shown in Figure 2.6(a), (b)
and (c), respectively, describe in English the language accepted by it.
2.2 Examples of Deterministic Finite Automata
In this section, we will develop some techniques to construct DFA’s through
examples. In each example, a language is given and we show how to construct
a DFA accepting the language.Example 2.6 (0 + 1)“.Solution. The language (0 + l) contains all binary strings. So, we simply
let the initial state be the final success state. The transition diagram of this
DFA is actually the same as the labeled digraph representation for the regular
expression (0 + l). We show it in Figure 2.7(a). (In a transition diagram, if
two edges have the same starting and ending vertices, we may merge them into