[Solved]: Prove or disprove: L^2 context free implies L is context free

Problem Detail: 

Clearly we have to disprove this. But I am finding it hard to prove it. I was trying in following way: Considering any non context free language L. I was trying to prove that L^2 is context free which will contradict given statement. But I don't know to how to prove it. Because by pumping lemma we can show only that language is not CFL but converse is not true. Can you please help me. Or is there any other way to prove it. Thanks

Asked By : Rohit

Answered By : Rick Decker

Ran's hint, with a bit of work, can indeed be used to show that the concatenation of an undecidable language with itself can be decidable. Here's a cute, simple, "almost-proof" of the fact that the concatenation of a non-CFL with itself can be a CFL:

1. The language $L=\{0^p\mid p \text{ is an odd prime}\}$ is not a CFL. This is a standard result, shown in some (but not all) theory texts.
2. Goldbach's conjecture: Any even number greater than 4 is the sum of two odd primes. This is unproven, but has been shown to be true for all even numbers less than $4\times 10^{18}$ and is regarded by many number theorists as likely true in general.

So, if Goldbach's conjecture is true, then $L^2=\{0^{2n}\mid n\ge 3\}$ which is clearly a CFL (being regular), even though $L$ isn't. Bada-bing.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33654

3.2K people like this

 Download Related Notes/Documents