Problem Solving in Automata, Languages, and Complexity

2.1 Deterministic Finite Automata 27

Figure 2.4: DFA of Example 2.5.

then comes back to ~0, it must have read five l’s, with an arbitrary number

of O’s in between any two 1’s. This means that a string IX: is accepted by M if

and only if the number of occurrences of symbol 1 in x is a multiple of 5. In

the form of a regular expression,

L(M) = o* (lo* 10* 10* 10* lo*)* l q

Exercise 2.1

1. Consider the DFA A4 with the transition diagram of Figure 2.5.

(a) Which state is the initial state of M, and which states are the final

states of M?

(b) For each of the strings 0001, 010101, and 001110101101, find the

computation path of A4 on the string and determine whether M

accepts it.

(c) Among all strings in (Ol)*, which ones are in L(M)?

Figure 2.5: DFA of Exercise 1.

2. For integers n, d > 1, consider a DFA A& d = (Q, X,6,40, F), where & =
   {qOl2~'*71~1}, c = {~01~''~~~-1}, 6(4i,ak) = q(di+k)modn>
   and F = {ql}.

(a) Draw the transition diagram of Mn,d with n = 7 and d = 2.