5
$\begingroup$

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.

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

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

$\endgroup$
  • $\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 Mar 27 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 Mar 27 at 18:31
  • $\begingroup$ Exactly, I just figured out how to prove the case of regular language. $\endgroup$ – Apass.Jack Mar 27 at 18:35

Your Answer

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

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