Due date: 4:00 P.M., Monday, March 2, 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. Work problem 3.8 on page 93 in the textbook. Write your answers here:

   (a)

   (b)

   (c)

   (d)

   (e)

   (f)

   (g)

   (h)

   (i)

   (j)

   (k)

   (l)

2. Work problem 2.44 on page 67 in the textbook. The problem reads,

   "Suppose that L, a subset of {a,b}*, is defined as follows: Lambda is in L; for every x,y in L, axby and bxay are both in L; nothing else is in L. Show that L is precisely the set of strings in {a,b}* with equal numbers of a's and b's."

   Hint: there are really two proofs here, first, to prove that every string in L has equal numbers of a's and b's, which is proved by strong induction, and is relatively easy, and second, to prove that every string over {a,b} with equal numbers of a's and b's is in L, which is also proved by strong induction, but is much harder. At one point in the proof, you will need to show that every string w with equal numbers of a's and b's which starts with an a has a prefix that has equal numbers of a's and b's and which ends with a b. That prefix can be chosen to be the smallest prefix of w which has equal numbers of a's and b's. (This is a very big hint.)

3. Work problem 5.35 in the textbook, but do not write down the proofs. Therefore, your answer in each case should be "regular" or "not regular."

   (a)

   (b)

   (c)

   (d)

   (e)

   (f)

   (g)

   (h)

   (i)

   (j)

   (k)

   (l)

   (m)

   (n)

   (o)

   (p)

4. Find an example of a language L over {0,1} such that L* is not regular.
5. Find an example of a language L over {a,b} such that L is not regular and L* is regular.
6. Find an example of a language L over {0,1} such that L is not regular and L^2 is regular.
7. Let L = {a^ib^j | 0 <= i <= j}
   1. Use the pumping lemma to prove that L is not regular.
   2. Prove that L is a context-free langugae, by giving a context-free grammar that generates L.