Description
1. (a) [10 points] Prove that for every pair of regular expressions, r1, r2, there exist a regular expression
r, such that L(r) = L(r1) \ L(r2). (For sets A, B, we define A \ B as {x : x ∈ A and x /∈ B}).
(b) [20 points] Find a regular expression r over Σ = {a, b}, such that L(r) = L((ab + b)
? + (ba +
b)
?
) \ L((b
?ab?
). Explain in detail how you constructed r and why it does the job.
2. (a) [10 points] Prove that for every finite set K of regular languages, ∩K is also a regular language.
(b) [Bonus 5 points] Does the previous claim remain valid if we allow K to be infinite? Prove your
claim.
3. Given a language L, define a language
P(L) = {w ∈ L : for every x, y, z, such that w = xyz, if y 6= then ∃i such that xyi
z /∈ L}
(a) [10 points] Prove that for every regular language L, the language P(L) is also regular.
(b) [10 points] Find language L for which P(L) is not a regular language.
4. For each of the following languages, determine whether they are regular or not. If they are, provide an
appropriate regular expression or an -NFA, or show how their existence follows from closure properties
that we have shown in class. If they are not regular, prove why.
(a) [10 points] L1 = {x ∈ {a, b}
?
: every occurrence of aaa in x is immediately followed by a longer
sequence of b
0
s }.
(b) [10 points] L3 = {x ∈ {a, b}
?
: na(x)−nb(x) = 2(mod5)}, (where, for a letter σ ∈ Σ, and a word
w ∈ Σ
∗
, nσ(w) denotes the number of occurrences of σ in w).
(c) [10 points] L4 = {a
k
b
l
c
m : l + k = m(mod3)}.
(d) [10 points] L5 = {(o1)k
(10)k
: k ∈ N}.
5. [Bonus 10 points] Let f be any function from the natural numbers to the natural numbers. Let L
be a regular language over some alphabet Σ such that, for every n ∈ N,
{w ∈ Σ
?
: f(n) ≤ |w| ≤ f(n) + n} ⊆ L
(that is, every word of length between f(n) and f(n) + n belongs to L). Prove that Σ? \ L is finite.
1