Context-Free languages not closed under complement

Summary:

An example for a CFL language who's complement is not CFL

Context-Free languages not closed under complement

Barak (guest) 30 Jun 2010 19:56

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 =)

Re: Context-Free languages not closed under complement

benny_chor 30 Jun 2010 20:52

At this stage, let us do an easier version of what you are after:
Define $L=\{w\$w\}$, where $w \in \{0,1\}^*$. With pumping, you can show that this language is not CFL.

What about its complement? We describe a non-deterministic PDA accepting it.
If the input string has zero or more than one dollar signs, it accepts.

If the input string is of the form $x\$y$, with x and y of different length (easily check this using the stack) it accepts.
If the input string is of the form $x\$y$ and for some i, $x_i\neq y_i$, it accepts (again the stack is used for counting: up from the beginning, guessing i and stop counting up,
then count down from the dollar sign).

This completes the job.

Of course I made life easier with the $. Without it you have to be a bit more sophisticated using guessing i, the middle, and the stack for verifying a
statement similar to the last task $x_i\neq y_i$ (counting from the middle, assuming even length).

Alternatively, you can generate the language (without dollar sign) using an appropriate grammar. I am pretty sure this grammar was shown by Rani and Jonathan somewhere
(but do not recall where).

Re: Context-Free languages not closed under complement

Barak (guest) 01 Jul 2010 12:57

Thanks for the quick response =)

The $ sign does indeed make it possible to find a sane solution, although I still don't seem to understand how to do this withour the $ symbol (validating what should be the middle of the string while counting is what I failed to do in the first place - since basically I need to keep 2 counters ($i$ from the begining, and half length) using one stack, and I need to be able to count $i$ after I push $l$ and the problem is that I can't pop $l - i$ values in order to find $i$)

I'll try and look for the grammar to do this (I don't remember Rani showed it, but maybe I just forgot it so I'll look again).
If it's possible, I would still like (since it sounds very interesting) to see the PDA to do this without the dollar symbol.

by the way, this level of PDA's is too hard to be included on a test, right?

Thanks again

Re: Context-Free languages not closed under complement

Jonathancito 01 Jul 2010 14:39

Hi,
It's hard to say what's hard or too easy, this is definitely hard but it appeared on some tests, I assume when a variation of this was done in class or in an exercise.

About doing it without the '$' here is a hint.

Convince yourself that the following claim is true:

A word is not of the form ww if and only if (a) either it is of an odd length (b) or it is a concatenation of two words x and y, such that |x| and |y| is odd (as in opposed to even), and the middle character of x is different than the middle character of y (the middle exists since they are of odd length).

Now you can:

1. Think why this claim is true - hint: the middle character that is different is exactly the character that makes xy not of the form ww.

2. Think of a CFG generating the language in its alternative description

Re: Context-Free languages not closed under complement

Yotam (guest) 01 Jul 2010 15:03

If I understood the question correctly, you can also use the solutions to ex#3, question 1(c):
http://tau-cm.wdfiles.com/local--files/home-assignments/sol3.pdf