1. Give the state diagrams of DFAs recognizing the following languages over = {0, 1}: a. {w : w has prefix 110} b. {w : w has suffix 001} c. {w : w contains the substring 101} 2. Give the state diagrams of DFAs recognizing the following languages over = {0, 1}: a. {w : w does not contain substring 10} b. {w : every odd position of w is a 1} c. {w : w contains at least one 0 and at least one 1} 3. Give a constructive proof to show that a DFA Mk = (Qk, k, k, q0, Fk) exists that recognizes each Lk = {w: w ends in k 1s} (for all k > 0) over = {0, 1. 4. Each of the following languages are composed of two simpler languages over the alphabet = {a, b, c}. For both, construct the DFAs for the simpler languages, then combine them using the construction of the closure proof presented in lecture (and page 46 of text): a. {w : w starts with a and has at most one b} b. {w : w has an odd number of bs or ends in c} 5. Give a constructive proof that set difference is a closure for regular languages.