# Does the following transformation preserve context-freeness?

I encountered this problem involving manipulating a context-free language. Let $L$ be a context-free language. Define $L^{\#} = \{ x : x^i \in L$ for every $i=0,1,2,...\}$. Is $L^{\#}$ always context-free?
My guess is that it will preserve context-freeness. Can anyone provide an elementary proof of this?

• When you post a question on two sites, people appreciate it if you leave a comment about the cross-posting, linking to the question on the other site. – Tara B Mar 1 '13 at 21:00
• Comment: for regular languages this is correct. Let $L\in REG$, so $L$ has a DFA with $n$ states, then for every word $x$, if $x,x^2,...,x^{n+1}$ are all in $L$, then $x\in L^\#$, so we can construct a DFA that recognizes $L^\#$. The usage of the finite-ness of the DFA here suggests that the claim may not be true for CFLs. – Shaull Mar 1 '13 at 21:11
• student.cs.uwaterloo.ca/~cs462 Problem set 7. I wanted to add the homework tag, but that didn't work (?) – Hendrik Jan Mar 1 '13 at 21:20
• @HendrikJan It looks like they don't have the homework tag here – Vitaly Olegovitch Mar 1 '13 at 22:04
• @VitalijZadneprovskij So it seems! Solution is due March 5 2013. So I will answer next Wednesday, when still needed. Great problem though. – Hendrik Jan Mar 1 '13 at 22:08

Counter-example:

$L_1 = \{a^n b^n c^m \mid m,n \ge 1 \}$

$L_2 = \{a^m b^n c^n \mid m,n \ge 1 \}$

$L = (L_1 \cdot L_2^*) \cup \epsilon$ is context-free.

Any nonempty word $x \in L^\#$ has a prefix $p = a^n b^n c^m \in L_1$. It must be $n = m$, because due to $L_2$, any pair of a $b^+$ and a directly succeeding $c^+$ in $x$ (after $p$) must share the same exponent. Therefore:

$L^\# = (\{a^n b^n c^n \mid n \ge 1 \} \cdot L_2^*) \cup \epsilon$, which is not context-free.

• I'm not sure if I understand what you want to say. A string like $x = a^n b^n c^n a^k b^k c^k$ is in $L^\#$ because $a^n b^n c^n \in L_1,L_2$ and $a^k b^k c^k \in L_2$, so you can produce all powers of $x$ with $x^2 \in L_1 L_2 L_2 L_2 \subset L$ and so forth. – Simon S Mar 7 '13 at 17:06
• However I realized I put $L^\#$ wrong in some way. – Simon S Mar 7 '13 at 17:21
• Indeed, I was missing some strings, but my arguments were not clear, I agree, and probably wrong as written. Now it looks fine to me. Thanks. I delete that comment now. – Hendrik Jan Mar 8 '13 at 11:21