¿Existen permutaciones $\pi_1,\pi_2$ y CFG de tamaño polinómico que describen el lenguaje finito $\{w \pi_1(w) \pi_2(w)\}$ sobre el alfabeto {0,1}?

Question

¿Existen permutaciones $\pi_1,\pi_2$ y CFG de tamaño polinómico que describen el lenguaje finito { $w \pi_1(w) \pi_2(w)$ sobre el alfabeto {0,1}?

Tamaño polinómico en $|w|=n$

Answer 1

Sin pérdida de generalidad, podemos suponer que una gramática para $L_n$ (como una lengua con un $\pi_1,\pi_2 \in S_n$ ) está en la forma normal de Chomsky. El lenguaje $L_n$ consiste en las palabras $w(x) = x\pi_1(x)\pi_2(x)$ para todos $x \in \{0,1\}^n$ .

Utilizando el lema de las subpalabras (ver mis respuestas anteriores), para cada $w(x)$ podemos encontrar una subcadena $s(x)$ de longitud $$\frac{n}{2} \leq |s(x)| < n$$ generado por algún símbolo $A(x)$ y que se produce en la posición $p(x)$ .

Supongamos que $p(x) = p(y)$ y $A(x) = A(y)$ . Desde $|s(x)|<n$ la subpalabra $s(x)$ no puede intersecar tanto el $x$ parte y la $\pi_2(x)$ parte de $w(x)$ podemos suponer que es disjunta de la $x$ parte. Así, $w(x)$ es de la forma $x \alpha s(x) \beta$ . Esto implica que $A(x)$ genera exactamente una cadena, a saber $s(x)$ . Por lo tanto, $s(x) = s(y)$ .

Ahora $s(y)$ se cruza con $\pi_1(y)$ o $\pi_2(y)$ en al menos $n/4$ lugares, y por lo tanto determina al menos $n/4$ bits de $y$ . Por lo tanto, como máximo $2^{3n/4}$ cuerdas $y \in \{0,1\}^n$ puede tener $p(x) = p(y)$ y $A(x) = A(y)$ . Dado que hay como máximo $3n$ posibilidades de $p(y)$ , obtenemos que hay al menos $$\frac{2^{n/4}}{3n}$$ diferentes no-terminales en la gramática.

Comentario: La misma prueba funciona si $\pi_1,\pi_2 \in S_{\{0,1\}^n}$ es decir, son permutaciones arbitrarias en el conjunto de todos los $n$ -palabras de bits. Dado $n/4$ bits de $\pi_i(y)$ Hay exactamente $2^{3n/4}$ preimágenes $y$ .