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

$\begingroup$

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?

$\endgroup$

1 Answer

$\begingroup$

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 if 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^*$.

$\endgroup$ 7

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy