Description
1. (20 points) Let L1 and L2 be languages and define
shuffle(L1, L2) = {x1 y1 x2 y2 . . . xn yn | x1 . . . xn ∈ L1, y1 . . . yn ∈ L2}.
Show that if the language L1 is not regular and L2 is any language then the languages
shuffle(L1, L2) and shuffle(L1, L2) cannot both be regular. Recall for any language L, L = Σ∗ \ L
denotes the complement language of L.
Hint: Recall closure properties of regular languages.
2. (40 points) In this problem we investigate the limits of the Pumping Lemma as it was stated in
class and look for an alternative that remedies one of these shortcomings.
(a) (10 points) Let L1 be the language
L1 = {a
i
b
p
| i ≥ 0 and p is a prime}.
Prove that the language L2 = b
∗ ∪ L1 satisfies the conditions of the Pumping Lemma. I.e.
show that there exists a q ∈ N such that for every word w ∈ L2 with |w| ≥ q we can write
w = xyz such that |xy| ≤ q, |y| > 0, and for every i ≥ 0, xyi
z ∈ L2.
(b) (20 points) Prove the following generalization of the Pumping Lemma:
Let L be a regular language. There exists a q ∈ N such that for every w ∈ L and every
partition of w into w = xyz with |y| ≥ q there are strings a, b, c such that y = abc, |b| > 0,
and for all i ≥ 0, xabi
cz ∈ L.
(c) (10 points) Prove that the language L2 is not regular.
3. (40 points) For a language L over alphabet Σ, we define
L1
3 − 1
3
= {xz ∈ Σ
∗
| ∃y ∈ Σ
∗ with |x| = |y| = |z| such that xyz ∈ L}.
Prove that if L is regular, then L1
3 − 1
3
need not be regular.
Hint: Consider the language 0
∗21∗ and recall closure properties of regular languages
2