HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Prove or disprove: L^2 context free implies L is context free

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
freeimpliesprovecontextdisprove

Problem

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

Solution

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.

Context

StackExchange Computer Science Q#33654, answer score: 2

Revisions (0)

No revisions yet.