0

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?

Tawcher Bro
  • 41

1 Answers1

2

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

Brian M. Scott
  • 616,228
  • Well, suppose L0={a^n b^n c^n | n≥1}. That is not context-free and we can prove with pumping lemma....But {a,b,c}∪L0 will still fail while applying pumping lemma, which means {a,b,c}∪L0 is actually not context-free as well. – Tawcher Bro Jul 19 '20 at 03:31
  • Can you please give more details? Since L*=L+L+L...not L∪L. Sorry but I cannot get your point. – Tawcher Bro Jul 19 '20 at 03:32
  • @TawcherBro: Of course ${a,b,c}\cup L_0$ is not context-free: that’s exactly the point! Now, what is the language $L^$? It’s very simple, and you should be able to tell me exactly what words are in it and from that what kind of language it is. An added hint: you don’t need to know anything about $L_0$ to figure out what $L^$ is. – Brian M. Scott Jul 19 '20 at 03:37
  • Then the expression that can be accepted by L* can be arbitrary combination of {a,b,c}, and L* can be represented by something like S->ε|aS|bS|cS, so it is context-free even if L is not. Did I get it? – Tawcher Bro Jul 19 '20 at 03:52
  • @TawcherBro: Yes: $L^={a,b,c}^$, and that language is not just context-free, but even regular. Thus, taking the Kleene star of a language $L$ can give you a language that is as nice as possible even when $L$ is very complicated. – Brian M. Scott Jul 19 '20 at 03:52
  • Fantastic. Thanks so much ! Sometimes I really feel that I am using inspiration rather than my poor experience to solve problems related to computing theory. They are still like some magic XD. – Tawcher Bro Jul 19 '20 at 04:03
  • @TawcherBro: You’re welcome! – Brian M. Scott Jul 19 '20 at 04:06
  • 1
    Nice argument, but it works equally well with a one letter alphabet. – J.-E. Pin Jan 14 '24 at 22:23
  • @J.-E.Pin: And at this point I have no idea why I rather arbitrarily used a 3-letter alphabet. – Brian M. Scott Jan 14 '24 at 23:07