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?

  • $\begingroup$ 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. $\endgroup$
    – Tara B
    Mar 1 '13 at 21:00
  • 2
    $\begingroup$ 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. $\endgroup$
    – Shaull
    Mar 1 '13 at 21:11
  • $\begingroup$ student.cs.uwaterloo.ca/~cs462 Problem set 7. I wanted to add the homework tag, but that didn't work (?) $\endgroup$ Mar 1 '13 at 21:20
  • $\begingroup$ @HendrikJan It looks like they don't have the homework tag here $\endgroup$ Mar 1 '13 at 22:04
  • 1
    $\begingroup$ @VitalijZadneprovskij So it seems! Solution is due March 5 2013. So I will answer next Wednesday, when still needed. Great problem though. $\endgroup$ Mar 1 '13 at 22:08


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

  • $\begingroup$ 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. $\endgroup$
    – Simon S
    Mar 7 '13 at 17:06
  • $\begingroup$ However I realized I put $L^\#$ wrong in some way. $\endgroup$
    – Simon S
    Mar 7 '13 at 17:21
  • $\begingroup$ 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. $\endgroup$ Mar 8 '13 at 11:21

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.