1. Give state diagrams of DFAs recognizing the following languages.  In all parts the alphabet is {0, 1}.

(a)  {w | w has length at least 3 and its third symbol is a 0}

(b)  {w | w doesn’t contain the substring 110}

2. Give state diagrams of NFAs with the specified number of states recognizing each of the following languages. In all parts the alphabet is {0, 1}.

(a) The language {w  | w contains the substring 0101, i.e., w  = x0101y for some x and y} with five states.

(b) The language {w  | w contains an even number of 0s, or contains exactly two 1s} with six states.

3. For any string w = w1w2 . . . wn, the reverse of w, written wR , is the string w in reverse order, wn . . . w2w1 . For any language A, let AR  = {wR  | w ∈ A}. Show that if A is regular, then so is AR .

4. Let

Σ3 = (〈(「(l)        l(」) )〉) .

Σ3  contains all size 3 colums of 0s and 1s.  A string of symbols in Σ3  gives three rows of 0s and 1s. Consider each row to be a binary number and let

B = {w ∈ Σ3(*)|the bottom row of w is the sum of the top two rows}.

For example,

l 0(0) 」 「 1 l

l 0(1) 」 「 0 l

「 0 l ∈ B, but

l 0(0) 」 「 1 l

「 1 l \∈ B .