If L* is context-free, is L context-free as well?

Question

I know CFL in closed under Closure, but don't know how to prove it back.

I try to construct a CFG for L* such as S->ε|AS and say since L* in a context-free language, there must exist a method to build grammar A. So then we can use A to construct another CFG to represent L and prove L must be context-free.

But I believe it is not a convincing proof. Can anyone please give some proof or counter example?

Answer 1

HINT: Let $L_0$ be a language over $\{a,b,c\}$ that is not context-free, and let $L=\{a,b,c\}\cup L_0$, which is of course also not context-free. What is $L^*$? Note that it is possible to answer this without knowing anything about $L_0$ beyond the fact that it is over the alphabet $\{a,b,c\}$.

I’ve added a further hint in the spoiler-protected block below; mouse over it to see it.

Since the alphabet $\{a,b,c\}$ is a subset of $L$, clearly $\{a,b,c\}^*\subseteq L^*$.