By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
438,470 Members | 1,907 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 438,470 IT Pros & Developers. It's quick & easy.

Pumping Lemma for CFLs

P: n/a
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.
Jul 17 '05 #1
Share this Question
Share on Google+
1 Reply


P: n/a
On 5 Nov 2003, Jack Smith wrote:
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.


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

Jul 17 '05 #2

This discussion thread is closed

Replies have been disabled for this discussion.