## 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