1. (10 points) Consider the FA M given below: a,b 90 92 a. Write a formal definition of Mi. b. Consider strings bab, abaa, abab, E. Which ones are accepted by M,? Show the traces of strings in L(M2). C. Explain, i.e., describe, what is the language recognized by M. 2. (15 points) Build a deterministic FA M2 for the following language L2 = {x over {a, b} | x consists of sequences of two identical symbols). For example, aab & L2 and ab L2, but bb E L2 and bbaaaabb E L2. 3. (15 points) Build a deterministic FA M3 such that L(M3) = {w over {a,b}||w| 21, length of w is even, and w ends on b}. 4. (15 points) Build a deterministic FA M4 for the following language La = {x over {a, b} if x contains sequences of a's then all of them must have odd length} For example, aa L2 and babbaaaa 4, but be La E Laba e L and bbaaab e L4. (Hint: in constructing each deterministic FA for problems 2, 3, and 4 make sure to consider all the possibilities, i.e., the different types of strings in the language of the corresponding FA.)