Pumping Lemma for CFLs

[Jack Smith]

Hello,

I need to show the following language is NOT context-free, using the
pumping lemma for context-free languages.

L = {wwdouble(w) | w is an element of {a,b}*}, where double(w) is
derived from w by doubling each symbol, e.g. for w = aba, double(w) =
aabbaa.


Now I know I can use the pumping lemma directly on this language, but
then there are too many cases. I was wondering if anyone knows how I
can show this using the pumping lemma in conjunction with closure
properties for CFLs (i.e. using the pumping lemma to show a simpler
language K is not context free. And then showing that if K is not
context free then, L cannot be context free).

e.g. Assume L is context-free

Let G be some CFL.

Then L?G = K should be context free, but we showed it is not using
pumping lemma => contradiction, thus L cannot be context free.

(where ? is some CFL closure property)

I am having trouble on figuring out which closure property to use and
which language K to use. Any help is appreciated.

Thanks in advance.

[Jim Nastos]

Re: Pumping Lemma for CFLs

On 5 Nov 2003, Jack Smith wrote:
[color=blue]
> I need to show the following language is NOT context-free, using the
> pumping lemma for context-free languages.
>
> I am having trouble on figuring out which closure property to use and
> which language K to use. Any help is appreciated.[/color]

Since you say that you need to show the language is CF *using the
pumping lemma*, don't bother with the closure properties.
Plus, what do all the closure properties tell you? You had condition 1
and condition 2, then something is CF. Do you know of any closure property
which concludes that something is NOT CF?
You say your pumping lemma proof has "too many cases," but it is usually
quite easy to group many cases into one and just deal with 3 or 4... I
haven't tried with wwdouble(w), but I don't think this should be too hard.
Why don't you try giving us your cases? Or at least what string you are
trying to pump on.

J