In lecture 5 slide 18, there is an example for a language which is not CFL, but it's complement should be a CFL.
I tried to proove it's a CFL for several hours but I had no luck…
This is the part which is giving me trouble:
Given a string $x$ of even length, we need to test with a PDA that no $\omega \in \Sigma^*$ exists so that $x=\omega\omega$. The slides suggest guessing non-deterministically a position $i$ so that $x_i \neq x_{i+l}$ (where $l$ is the length of $\omega$).
The problem is, that I can't find a way to do this - making a progress of $l$ places before we know the length of the string (which is $2l$) doesn't work for me, and I haven't found a way to progress $l$ places and still compare the character at some place $i$.
I can't explain this very well, but where they said in the slide "voluntary home assignment: fill in the details!", I simply can't fill in the details formally. It always get's stuck somewhere… If anyone can proove this is a CFL (or maybe that it's not) I'll be very thankful =)