Due date: 4:00 P.M., Wednesday, February 11, 1998.

If you cannot attend class that day, leave your homework, in an envelope, with one of the office staff, on or before Wednesday.

Please work your homework only on these pages, and turn in these pages. Do not attach extra pages. You may use one side or both sides of the paper. Use pen or pencil, any color except red. If you use pen, it is perfectly correct to simply cross out material I should ignore, rather than try to erase it. Do not fold your papers at all. If you put them in an envelope, the envelope should be 9 by 12.

You are permitted to discuss homework with other members of the class, or others outside the class. But the purpose of this discussion should be to enlighten you (or the other person, if a member of the class) about the material, not for one person to simply do another person's homework.

1. Let Sigma = {a,b}. How many strings are there over Sigma of length no greater than 2? List those strings in any order.
2. Let Sigma = {a,b}. Let L be the language over Sigma consisting of all strings which end with aa. Draw an NFA with only three states and four transitions which accepts L.
3. Let M be the NFA you constructed for problem 2. Construct a DFA equivalent to M.
4. Let L be the language over {0,1} consisting of all strings which are binary numerals for multiples of 3. That is, L = {0,11,110,1001,1100,1111, . . . }. Write a regular expression for L.
5. If L_1 and L_2 are languages, and if L_1* = L_2* (The Kleene closures of L_1 and L_2 are equal), prove that L_1 = L_2.