Problem 1: We know the difference of two context-free languages need not be context free. Suppose we take the difference of a regular language R and a context-free language L. There are two ways to take the difference. Is R-C necessarily context-free? Is C-R necessarily context free? Justify your answers informally, but giving the key ideas.

Problem 2: The operation Half(L) from Exercise 4.2.8 in the text is { w | for some x with the same length as w, wx is in L}. While regular languages are closed under Half, CFL's are not. Give an example of a CFL L such that Half(L) is not a CFL. Prove that your language L is a CFL by describing a CFG or PDA for L. Prove that Half(L) is not a CFL by whatever means are appropriate, e.g., using the pumping lemma and/or applying some CFL-preserving operation to Half(L) to produce a language known not to be a CFL. A Hint is available.