Revised CSE 322 Assignment #5
Spring 2000

Due: Friday, May 5, 2000

Reading assignment: Read Lewis and Papadimitriou 2.5, 3.1

Problems:

1. For each of the following languages show that it is not regular (i) using the pumping lemma (ii) using the Myhill-Nerode theorem as in example 2.5.2 of the text.

   1. { w | w=w^R }

   2. { a^mbⁿ | m >=n }

   3. { a²ⁿ | n>= 0}

2. Lewis and Papadimitriou problem 2.4.2 page 90.

3. (Bonus) Show that the pumping lemma cannot be used to show that

   { aⁱ b^j c^k | i, j, k >= 0, and if i = 1 then j = k }

   is not regular but show that the Myhill-Nerode can be used to prove that it isn't regular.

4. (Bonus) Lewis and Papadimitriou problem 2.4.12 page 92.