Sipser Exercise 2.41


Define operations on languages:

(a) Theorem: Context-free languages are not closed under or .


Proof: To construct a counterexample, we must start with some CFL whose whose complement fails to be context-free. So let . We showed was context-free in the past, and of course its complement is not.

Now, introduce a new unique alphabet symbol and construct the following new languages:

So includes everything in appended with a , but also includes copies of the members of decorated with an extra . Similarly, includes every string in appended with two ’s, but also includes copies of the members of with one less .

These languages are context-free. We can see this by machine construction. Start with a PDA for (that accepts by final state). To construct a machine for , add an transition from every state of to a state that waits for 1 before accepting, and add an transition from the final states of to a state that waits for 2 ’s before accepting. Similarly, do the opposite to construct a machine for .

Now consider . A string in has no extensions in if and only if is not in (otherwise, we could add another to get another string in ). That is, we have . It follows from the fact that is not context-free that this is not context-free, so is a counterexample for .

Now, consider . A string in has no prefix in if and only if is not in (otherwise, we could remove the last to get another string in ). That is, we have , and similarly it follows that this is not context-free, so is a counterexample for .