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.