CPTR 324 Spring 2006 Exam 2 Name ________________________

1. Give an example of a language that is context-free but not regular. (4 points)

2. Give an example of a language that is not contex- free. (4 points)

3. A context-free grammar G is formally defined as a 4-tuple

G = (V, S, R, S)

Define (or describe) each of the 4 components. (4 points)

4. Show that the following context-free 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 context-free 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 context-free 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 context-free. HINT: You may use any method. However, using the following two facts can lead to a very short answer: (5 points)

§ If C is context-free and R is regular, then C Ç R is context-free.

§ The language B = {0ⁿ1²ⁿ0ⁿ | n ³ 0} is not context-free.

13. Use the Pumping Lemma to prove that L = {aⁿbⁿaⁿbⁿ | n ³ 0} is not a CFL. (10 points)