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.


2 Answers 2


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

  • $\begingroup$ @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. $\endgroup$
    – sdcvvc
    Commented Mar 27, 2019 at 17:30
  • $\begingroup$ @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. $\endgroup$
    – sdcvvc
    Commented Mar 27, 2019 at 18:31

Take the language $L = \{a^{n^2} \colon n \ge 1\}$, it is easy to prove non-regular (and non-context-free). However, $L^*$ is the language denoted by $a^*$, which is regular (and thus context free).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.