¿La siguiente transformación preserva la ausencia de contexto?

Question

Me encontré con este problema que implica la manipulación de un lenguaje sin contexto. Permita que$L$ sea un lenguaje sin contexto. Defina$L^{\#} = \{ x : x^i \in L$ para cada$i=0,1,2,...\}$. ¿Es$L^{\#}$ siempre libre de contexto?
Mi suposición es que preservará la ausencia de contexto. ¿Alguien puede proporcionar una prueba primaria de esto?

Answer 1

Tome$\Sigma$ = {$a,b,c$} y$L=$ {$a^nb^nc(a^*b^*c)^*:n\geq0$}.

Ahora, L es claramente libre de contexto ya que es una concatenación entre un lenguaje libre de contexto y un lenguaje regular.

Sin embargo,$L$ # = {$(a^nb^nc(a^*b^*c)^*)^k:n\geq0,k\geq0$}, que se puede mostrar, utilizando el lema de bombeo, no debe estar libre de contexto.

Entonces, el reclamo es falso.

Espero que mi razonamiento sea correcto.