Assigned:
Wed 04 Feb 2004
Due:
Wed 11 Feb 2004
Problem | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | ... |
---|---|---|---|---|---|---|---|---|---|---|
Credit | RC | RC | RC | EC | RC | RC | NA | RC | RC | ... |
where "RC" is "regular credit", "EC" is "extra credit", and "NA" is "not applicable" (not attempted). Failure to do so will result in an arbitrary set of problems being graded for regular credit, no problems being graded for extra credit, and a five percent penalty assessment.
Required: 5 of the following 7 problems
Points: 20 pts per problem
Note: "!=" is "not equal."
Note: Satisfying the conditions of the strong Pumping Lemma implies satisfication of the conditions of the standard Pumping Lemma.
Ogden's Lemma: Let L be an context-free language. Then there exists a constant k such that if w is any string in L, |w| >= k, and we mark any k or more positions of w as "distinguished," then w may be divided into five pieces w = uvxyz satisfying the conditions:
Hint: Consider the string akbkck+k!.
Hint: Construct a CFL A such that all strings in FirstHalf(A) which end in a single # must have the form anbncn#.