I'm looking for a CFL whos complement is not a CFL.

any good ideas for a simple one?

Another(yet, maybe more simple) example might be $\{0^n1^n2^n\}$ which is not a CFL.

What is the complement? well, it's all the worlds which are not even in the form of $0^*1^*2^*$, union with $\{0^n1^m2^k | n \ne m \lor n \ne k \lor m \ne k \}$ which is a CFL (is it the one from the midterm?)

The complement of {ww}. {ww} is not CFL, while Sigma*/{ww} is.

do you have a formal proof for it?

i know the basic idea (slide 26 of lecture 5), but i couldn't close the details.

Most formal proof I've found, from Stack-Overflow (can't post a link..):

S→A|B|AB|BA

A→a|aAa|aAb|bAb|bAa

B→b|aBa|aBb|bBb|bBa

A generates words of odd length with a in the center. Same for B and b.

I'll present a proof that this grammar is correct. Let L={a,b}∗∖{ww∣w∈{a,b}∗} (the language in the question).

Theorem. L=L(S). In other words, this grammar generates the language in the question.

Proof. This certainly holds for all odd-length words, since this grammar generates all odd-lengths words, as does L. So let's focus on even-length words.

Suppose x∈L has even length. I'll show that x∈L(G). In particular, I claim that x can be written in the form x=uv, where both u and v have odd length and have different central letters. Thus x can be derived from either AB or BA (according to whether u's central letter is a or b). Justification of claim: Let the ith letter of x be denoted xi, so that x=x1x2⋯xn. Then since x is not in {ww∣w∈{a,b}n/2}, there must exist some index i such that xi≠xi+n/2. Consequently we can take u=x1⋯x2i−1 and v=x2i⋯xn; the central letter of u will be xi, and the central letter of v will be xi+n/2, so by construction u,v have different central letters.

Next suppose x∈L(G) has even length. I'll show that we must have x∈L. If x has even length, it must be derivable from either AB or BA; without loss of generality, suppose it is derivable from AB, and x=uv where u is derivable from A and v is derivable from B. If u,v have the same lengths, then we must have u≠v (since they have different central letters), so x∉{ww∣w∈{a,b}∗}. So suppose u,v have different lengths, say length ℓ and n−ℓ respectively. Then their central letters are u(ℓ+1)/2 and v(n−ℓ+1)/2. The fact that u,v have different central letters means that u(ℓ+1)/2≠v(n−ℓ+1)/2. Since x=uv, this means that x(ℓ+1)/2≠x(n+ℓ+1)/2. If we attempt to decompose x as x=ww′ where w,w′ have the same length, then we'll discover that w(ℓ+1)/2=x(ℓ+1)/2≠x(n+ℓ+1)/2=w′(ℓ+1)/2, i.e., w≠w′, so x∉{ww∣w∈{a,b}∗}. In particular, it follows that x∈L.