(1) Write \graf code for a DFA M_1 that recognizes the @lang of strings over \S={a,b} such that the length of each string is congruent to 1 modulo 3. //

(2) Use the @deftn of \d* to prove whether the string *{aba} is accepted by M_1. Show all of the steps of \d*. //

(3) Write \graf code for a DFA M_2 that recognizes the @lang of strings over \S={a,b} that do not have 2 consecutive *{a}s. //

(4) Modify the !{process from class} for taking the union of two DFAs to write \graf code for a DFA M_3 such that L(M_3)=L(M_1) L(M_2). What did you change about the process? Why does that work in general? //

(5) Use words to describe L(M_3). //

(6) Use words to describe ~{L(M_3)}. //

(7) Write \graf code for a DFA M_4 that recognizes ~{L(M_3)}. How would you recognize the complement of the @lang recognized by a DFA in a generalized process? What makes your process work? //

(8) Use the !{mathematical induction} and the definition (from \graf) of the *{reverse of a string} to prove the following:

>< If v and w are strings over \S, then (v\.w)^{R}=w^{R}\.v^{R}.