Description
1. [20 Points] For each of the following languages over Σ = {a, b}, write a regular grammar
and then convert it into an equivalent NFA using the procedure described in class.
(a) (10 Points) L(r) where r = ((a + b)(a + b))∗
b + a((a + b)(a + b))∗
; and
(b) (10 Points) {w ∈ {a, b}
∗
: w ends in a and |w| ≡ 1 (mod 3)}.
2. [25 Points] Fix an alphabet Σ. For any string w with |w| ≥ 2, let skip(w) be the string
obtained by removing the first two symbols of w. Define two operators on languages:
f1(L) = {w ∈ Σ
∗
: skip(w) ∈ L}, and
f2(L) = {skip(w) ∈ Σ
∗
: w ∈ L}
(a) (5 Points) Consider L
0 = L(bba∗
) over the alphabet Σ = {a, b}. Write a regular
expression representing f1(L
0
). Write another regular expression representing
f2(L
0
).
(b) (10 Points) Claim: for every regular language L the language f1(L) is regular.
Clearly state whether the claim is TRUE or FALSE, and then prove your answer.
(c) (10 Points) Claim: for every regular language L the language f2(L) is regular.
Clearly state whether the claim is TRUE or FALSE, and then prove your answer.
3. [20 Points] For each of the following languages, use the Pumping Lemma and/or closure
properties of regular languages to show that the language is not regular.
(a) (10 Points) L1 = {0
k1
`
: k ≥ `
4 ≥ 0}.
(b) (10 Points) L2 = {a
n
: n is not a perfect cube}.
