CPTR
324 Spring 2006 Exam 2 Name ________________________
1. Give an example of a
language that is contextfree but not
regular. (4 points)
2. Give an example of a
language that is not contex free. (4 points)
3. A contextfree grammar
G is formally defined as a 4tuple
G = (V, S, R, S)
Define (or describe) each of
the 4 components. (4 points)
4. Show that the following
contextfree grammar is ambiguous. (5 points)
S ® aSb  A  e
A ® aA  B
B ® Bb  e
5. Consider the following
grammar:
S ® aSa  XY
X ® bXb  e
Y ® cYc  e
(a) Give the leftmost derivation
for the string aabbccaa. (5
points)
(b) Give the corresponding parse
tree for that derivation. (5 points)
(c) What language is generated by
the grammar? (5 points)
6. Matching:
For each of the transitions below, match it to the description that best
describes it. (8 points)
a. pop the stack based on the input
b. pop the stack regardless of the input
c. push that ignores the input and stack
d. push based on a given input but ignoring the stack
e. replaces the top stack symbol, based on the input and
current stack symbol
f.
replaces the top
stack symbol regardless of the input
g. reads the input but leaves the stack alone
h. makes a guess
7. Draw the transitions
necessary to implement the following processing: If the PDA is in state p and there’s an X on the
top of the stack and an a on the
input, replace the X with a Y and the
push on two Z’s, and ending in
state q. (5 points)
8. Consider the following PDA.
a. Give 3 strings accepted by
the PDA. (6 points)
b. What is the language accepted by
the PDA. (4 points)
9. Indicate for each of the
following operations (by placing an X in the appropriate column) whether or not
the class of contextfree languages is closed under that operation. (10 points)
operation 
closed 
not closed 
complement 


concatenation 


intersection 


star 


union 


10. Let S = {a, b}. Show that the language{w  the length of w is
odd and its middle symbol is a} is a
CFL by giving a contextfree grammar for it.
You only need to give the production rules. (10 points)
11. Give a PDA for the language
in the previous question. You only need
to give the transition diagram. (10
points)
12. Let A be the language of all palindromes over {0, 1} containing an
equal number of 0s and 1s. Show that A
is not contextfree. HINT:
You may use any method. However, using
the following two facts can lead to a very short answer: (5 points)
§
If C is contextfree and R is regular, then C Η R is contextfree.
§
The language B = {0^{n}1^{2n}0^{n} 
n ³ 0} is not contextfree.
13. Use the Pumping Lemma to
prove that L = {a^{n}b^{n}a^{n}b^{n}  n ³ 0}
is not a CFL. (10 points)