a) Show that the following language is not regular:

L= {a^n : n is composite}.

(Hint: Consider first the corresponding language with n prime.)

b) Recall the simple pumping lemme: If L is an infinite regular language, then any sufficiently long w L can be factored as w = xyz with y nonempty, so that xyzL. Show that this property holds for the language of a).

c) Can you find a similar example for the length-constrained pumping lemma (Sipser Thm. 1.3.7)?