9
$\begingroup$

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?

$\endgroup$
  • $\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$ – Hendrik Jan 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$ – Hendrik Jan Mar 1 '13 at 22:08
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\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$ – Hendrik Jan 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.