CSE 322 Assignment #4
Winter 1998

Due: Friday, February 6, 1998.

Reading assignment: Read Sipser's book, section 1.4 and finish up any parts of Chapter 1 you haven't read yet. The following problems are from the First Edition of the text.

Problems:

1. Page 86, Exercise 1.16.

2. Page 86, Exercise 1.17.

3. Page 86, Exercise 1.18.

4. Show that if A is regular then so is

   • PREF(A)={x | there is some y in SIGMA^* with xy in A}

   • SUFF(A)={y | there is some x in SIGMA^* with xy in A}

   • SUBSEQ(A)={y | there are some x, z in SIGMA^* with xyz in A}

5. Show that the language {aⁱ b^j c^k | i, j, k >= 0, and if i = 1 then j = k} satisfies the conditions of the pumping lemma even though it is not regular. Explain why this fact does not contradict the pumping lemma.

6. Page 90, Problem 1.41

7. (Bonus**) Page 90, Problem 1.42

8. (Bonus*) Prove that the language of non-palindromes (given in the original version of problem 1.37 page 89) does NOT satisfy the conditions of the pumping lemma.