**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 .