4
$\begingroup$

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

$\endgroup$
5
  • 4
    $\begingroup$ Take $L$ such that $L^2=\Sigma^*$. Does it mean $L$ must be CFL? Can you design such an $L$ that would be, say, undecidable? $\endgroup$
    – Ran G.
    Nov 30, 2014 at 19:49
  • $\begingroup$ @RanG. You should expand this into a (hinted) answer. $\endgroup$ Nov 30, 2014 at 20:54
  • 1
    $\begingroup$ possible duplicate of Is $A$ regular if $A^{2}$ is regular? $\endgroup$
    – Shaull
    Nov 30, 2014 at 21:25
  • 1
    $\begingroup$ @Shaull. Especially if one notes that a CFL over a 1-symbol alphabet is regular. $\endgroup$ Nov 30, 2014 at 21:29
  • 1
    $\begingroup$ If you need some heavy theory to show one question is a duplicate of another, it probably is a duplicate in the technical sense but not for out intended audience. $\endgroup$ Nov 30, 2014 at 21:43

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thanks. I was thinking about same way with prime numbers. But was not able to prove that L^2 is CFL. Anyways, I Goldbach's conjecture makes sense. Thank you for clearing this. $\endgroup$
    – Rohit
    Nov 30, 2014 at 22:14
  • $\begingroup$ Given that this is straightforward to prove unconditionally, I don't see why you'd want to prove it conditional on Goldbach. $\endgroup$ Dec 1, 2014 at 0:01
  • 1
    $\begingroup$ @DavidRicherby. No excuse except that it's cute. $\endgroup$ Dec 1, 2014 at 1:38
2
$\begingroup$

Hint. Let $U\subseteq\mathbb{N}$ be any undecidable set and let $I = \{2u+1\mid u\in U\} \cup \{0, 2, 4, \dots\}$. Let $L = \{a^i\mid i\in I\}$. Now prove that $L^2$ is context-free but $L$ is not.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.