CS3331 – Assignment 2
1. (30pt) Consider the alphanumeric alphabet Σ = {a, b, . . . , z, A, B, . . . , Z, 0, 1, . . . , 9} and let L be the
language of all regular expressions over Σ:
L = {w ∈
Σ ∪ {∅,(,), ∪, ·,
∗
}
?∗
| w is a syntactically legal regular expression over Σ} .
(a) Give an unambiguous context-free grammar that generates L. The grammar should use the
following precedence levels, from highest to lowest:
(1) ∗
(Kleene star) – highest precedence
(2) · (concatenation)
(3) ∪ (union) – lowest precedence
(b) Show the parse tree that your grammar produces for the string a(a ∪ b)
∗
.
2. (30pt) For each of the following languages L, prove whether L is regular, context-free but not
regular, or not context-free:
(a) L = {xy | x, y ∈ {a, b}
∗ and |x| = |y|}.
(b) {a
mb
n | m, n ≥ 0 and m ≥ 2n}.
(c) {w
RwwR | w ∈ {a, b, c}
∗}.
3. (10pt) Consider the language L = {wwR|w ∈ {a, b}
∗}. Below are two proofs, one showing L is
context free, the other showing the opposite. Which proof is correct and why?
L is context-free. Here is a context free grammar that generates L:
S −→ aA
A −→ Sa
S −→ bB
B −→ Sb
S −→ ε
L is not context-free. Consider the string wk = a
k
bbak ∈ L. Because |w| ≥ k, using pumping
theorem, wk can be written as wk = uvxyz. Put v = a
p
, y = a
q
, where at least one of p and q
is not 0. Then, according to the pumping theorem, uv2xy2
z ∈ L. But uv2xy2
z = a
k+p+q
bbak
cannot be written as wwR, for any string w, therefore uv2xy2
z 6∈ L, a contradition. This
implies that L is not context-free.
4. (30pt) Show that the following problem is decidable: Given a context-free grammar G, does G
generate any odd-length, nonempty strings?
Note Submit your solution as a pdf file on owl.uwo.ca.
