PROBLEM SET 4, CSC 280, 2006 DUE BEFORE CLASS, WED. FEB. 22 The fourth problem set is as follows. All 6 problems will be marked out of the same total. Answers to any 5 questions make a complete answer paper. However, you can do the remaining question to earn bonus points. TO FACILITATE THE GRADING PROCESS, PLEASE PUT YOUR ANSWERS TO SEPARATE QUESTIONS ON SEPARATE PAGES, AND PLACE YOUR ANSWERS IN THE SAME ORDER AS THE QUESTIONS, I.E., ANSWERS TO Q1, ANSWERS TO Q2, ETC. THANK YOU! Keep your eyes on the instructor's and the TAs' web site for any corrections or discussion. PROBLEM 1 ~~~~~~~~~ Use the pumping lemma to prove that {a^n | n = m² for some m >= 0} is not context-free Problem 2 ~~~~~~~~~ Use the pumping lemma to prove that each of the following two languages is not context-free (where a^i is a repeated i times, b^(2i) is b repeated 2i times, etc.): a. {a^ib^jc^id^j | i,j >= 0} b. {a^ib^(2i)a^i | i >= 0} Problem 3 ~~~~~~~~~ Use the pumping lemma to prove that {ww^Rw | w is in {a,b}*} is not context-free (where w^R is the reverse of w). PROBLEM 4 ~~~~~~~~~ a. Prove that L defined as {a^ib^(2i)c^j | i,j >= 0} is context-free b. Prove that L' defined as {a^jb^ic^(2i) | i,j >= 0} is context-free c. Prove that the intersection (L n L') is not context-free. PROBLEM 5 ~~~~~~~~~ Let L be the language of all strings over {a,b} containing the same number of a's as b's. Show that the pumping lemma is satisfied for L; i.e., show that every string w of length p or more (for some p) has has a decomposition that satisfies the conditions of the pumping lemma. PROBLEM 6 ~~~~~~~~~ A context-free grammar G = (V,Sigma,P,S) is called *linear* if every rule has one of the forms A -> u A -> uBv, where u,v are in Sigma* and A,B are in V. A language is called linear if it is generated by a linear grammar. Prove the following pumping lemma for linear languages. Let L be a linear language. Then there is a constant p such that for all w in L with |w| >= p, w can be written as uvxyz where (i) |uvyz| <= p (ii) |vy| > 0 (iii) uv^ixy^iz is in L, for all i >= 0. Hint: First get a clear sense of what the derivation trees for a linear grammar look like, and how application of a production adds to the length of the string ultimately generated. (Note: this lemma is easier to prove than the pumping lemma for arbitrary CFLs!)