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!)