Dejemos que $Σ=\{a,b,c\}$ . ¿Cuál de las siguientes afirmaciones es cierta?

Question

$1)$ Para cualquier $A\subseteq\Sigma^*$ , si $A$ es regular, entonces también lo es $\{x xx\in A\}$ .
$2)$ Para cualquier $A\subseteq\Sigma^*$ , si $A$ es libre de contexto, entonces también lo es $\{xxx\in A\}$

Según yo, el $1^\text{st}$ La afirmación debería ser correcta, pero no tengo ninguna pista respecto a $2^\text{nd}$ ya que si $xx$ es CFL entonces supongo $x$ también debería ser CFL , pero todavía estoy confundido con esta opción. No sé cómo enfocar esta cuestión.

Answer 1

Tienes razón en cuanto a la afirmación de las lenguas regulares. Se trata de un hecho bien conocido que suele expresarse con la frase de que los lenguajes regulares son cerrados bajo raíz cuadrada (por desgracia, la operación que describes se denota a veces incluso con $\sqrt{A}$ ) - los detalles de la prueba deberían ser fácilmente buscables en Google.

El caso de los lenguajes libres de contexto es más interesante. Tomemos el siguiente lenguaje: $$A = \{a^i b^i c^j a^n b^m c^m ~|~ i,j,n,m \in \mathbb{N};~i,j,n,m \geq 1\}.$$ La lengua $A$ es obviamente libre de contexto.

Ahora, el lenguaje $\{x ~|~ xx \in A\}$ contiene precisamente todas las palabras $x \in {\{a,b,c\}}^*$ , de tal manera que $xx = a^i b^i c^j a^n b^m c^m$ para algún tipo de $i,j,n,m$ . Obviamente, este es el caso si y sólo si $$x = a^i b^i c^j = a^n b^m c^m$$ para algunos $i,j,n,m$ . Pero esto implica directamente $i = j = n = m$ . Como resultado, la raíz cuadrada de $A$ contiene precisamente todas las palabras $x \in {\{a,b,c\}}^*$ , de tal manera que $x = a^n b^n c^n$ para algunos $n$ . Dicho de otro modo, $$\{x ~|~ xx \in A\} = \{a^n b^n c^n ~|~ n \in \mathbb{N};~n \geq 1\}.$$ Este lenguaje no está libre de contexto. Así que la familia de lenguajes libres de contexto no es cerrado bajo la raíz cuadrada .