# Is a kind of reverse Kleene star of a context-free language context-free?

Recently I had a question on one of my assignments asking to prove or disprove the following:

Let $$L$$ be a language. If $$L^*$$ is context-free then $$L$$ is context-free.

Now obviously this is false since we can take some non-context free language $$L_1$$ and the alphabet $$\Sigma$$, then make $$(L_1 \cup \Sigma)^* = \Sigma^*$$ is context-free and clearly $$L_1\cup \Sigma$$ is not.

Now I was thinking about a similar problem but now with respect to the words in the language, and was wondering if it is true or not. If $$C$$ is a context-free language then $$C'$$ is a context-free language where $$w\in C'$$ if and only if $$\{w\}^*$$ is contained in $$C$$.

My suspicion is that this is also false, but I can't come up with a counterexample. Somehow one needs to construct a CFL $$C$$ such that the subset of all the "periodic" words of $$C$$ together are not context-free.

• Deleting my answer. Apparently I took a construction which works for NFAs and extrapolated it to PDAs rather recklessly. – dkaeae Mar 27 '19 at 11:43
• What do you mean by "$w^*$ is contained in $C$"? $\{w^i\mid i\geq 0\}\subseteq C$? – David Richerby Mar 27 '19 at 12:20
• @DavidRicherby I just updated the question. (This comment will be deleted shortly.) – John L. Mar 27 '19 at 19:20

Let me solve a simpler question first. Suppose we'd like to know

If $$C$$ is context-free, must $$F(C)=\{w: ww \in C\}$$ be context-free?

The answer is no: $$F(\{a^i b^i c^j a^j b^k c^k\})=\{a^i b^i c^i\}$$.

As for the original problem, consider the context-free language that contains words of the form $$\{a^i b^i c^j d a^j b^k c^k d\}$$ or those which don't contain exactly two $$d$$'s.

Define $$D=\{w: w^\ast \subseteq C\}$$. Suppose $$D$$ is context-free. Then $$E=D\cap a^\ast b^\ast c^\ast d$$ is context-free.

I claim $$E=\{a^i b^i c^i d\}$$, which is not context-free. Suppose $$w = a^i b^j c^k d$$. We have $$w \in E$$ exactly if $$w^n \in C$$ for every $$n$$. This condition is clearly satisfied when $$n \neq 2$$, because $$w^n$$ will not have exactly two $$d$$'s. For $$n=2$$, $$w w=a^i b^j c^k d a^i b^j c^k d\in C$$ which is equivalent to $$i=j=k$$.

• @AlexPatterson Your language works too (nitpick: you need to add $\epsilon$). The argument with $d$'s seemed to be easier to explain and I didn't like dealing with $a^{+} b^{+} c^{+}$ vs $a^{\ast} b^{\ast} c^{\ast}$ but it's a matter of preference. In the second question, you are right that $j=j'$ is unnecessary. However, an analogous argument can be said about $i=i'$ and $k=k'$; you can skip any one of the 3 equalities, but not two of them. For symmetry, I prefer to have all three instead of skipping an arbitrary one. – sdcvvc Mar 27 '19 at 17:30
• @Apass.Jack It can be shown that if $C$ is regular, then $\{w:ww\in C\}$ and $\{w:w^\ast \subseteq C\}$ are also regular. – sdcvvc Mar 27 '19 at 18:31