CS 383

Homework, due on Wednesday 3/2

Here are some suggested problems to do:

p. 121   #3.4.1 parts (d), (f), (g)  #3.4.2 parts (a), (b), (d)

p. 129   #4.1.1 parts (a), (b), (c), (d), (e)  #4.1.2 parts (a), (e)

p. 145   #4.2.1 parts (a), (b), (c), (d), #4.2.2,  #4.2.4 parts (a), (c)

Here is a subset of these I would like you to hand in on Wednesday 3/2:

p. 129   #4.1.1 part (d)  #4.1.2 parts  (d), (e)

p. 145   #4.2.4 parts (a), (c).  You need to look at 4.2.2 for a definition of the symbols.

Also, I would like you to show that a language can satisfy the conditions of the Pumping Lemma

without being Regular.  Here is the example; you provide the details:

Let L1 be the language {b^jc^k: j, k >= 0}.  Let L2 be the language { ab^jc^j: j >= 0  }. 

Let L3 be { aⁱb^jc^k: i >= 2, j, k >= 0}.  Language L is the union of L1, L2, and L3.

a)      Show that L1 and L3 are regular but L2 is not.

b)      Show that every sufficiently long string in L is pumpable.

c)      Find a regular language R so that the intersection of L and R is L2.

d)      Show why (c) implies that L is not regular.