Description
1. [12 marks] This question develops a basic understanding of CFGs and parse trees. Consider the grammar G
below.
E → E + T | T (1)
T → T × F | F (2)
F → (E) | 2 (3)
For each string below, give a parse tree of a derivation in G.
(a) 2
(b) 2 + 2 + 2
(c) ((2 + 2) × (2))
2. [10 marks] We have seen in class that the sets of both regular and context-free languages are closed under the
union, concatenation, and star operations. We have also seen in A2 that the regular languages are closed under
intersection and complement. In this question, you will investigate whether the latter also holds for context-free
languages.
(a) Use the languages A = {a
mb
nc
n | m, n ≥ 0} and B = {a
nb
nc
m | m, n ≥ 0} to show that the class
of context-free languages is not closed under intersection. You may use the fact that the language C =
{a
nb
nc
n | n ≥ 0} is not context-free.
(b) Using part (a) above, show now that the set of context-free languages is not closed under complement.
3. [15 marks] This question develops your ability to design CFGs. For each of the following languages, give a
CFG. Assume the alphabet is Σ = {0, 1}. For string x = x1x2 · · · xn, we define x
R := xn · · · x2x1, i.e. this
operation reverses the order of the symbols in x.
Justify your answers briefly.
(a) {x | x starts and ends with the same symbol}.
(b) {x | the length of x is odd}.
(c)
x | x = x
R, that is, x is a palindrome
.
(d) ∅.
(e) For this part, set Σ = {a, b, $}. The language is then
x1$x2$ · · · $xk | k ≥ 1, each xi ∈ {a, b}
∗
, and for some i and j, xi = x
R
j
.
1
4. [15 marks] This question develops your ability to design PDAs. For parts (a), (b), (c), and (d) of question 3
above, give state diagrams of pushdown automata. For each automata, include a brief description of the idea
behind its design.
5. [10 marks] This question forces you to practice the generic construction for mapping a CFG to a PDA. Specifically, for the grammar G from question 1, use the construction from Theorem 2.20 to construct an equivalent
PDA P.
2