Es el complemento de {www | ...} sin contexto?

Es bien sabido que el complemento de tiene contexto. Pero, ¿qué pasa con el complemento de ?$\{ ww \mid w\in \Sigma^*\}$$\{ www \mid w\in \Sigma^*\}$

Todavía CFL, creo, con una adaptación de la prueba clásica. Aquí hay un boceto.

Considere $L = \{xyz : |x|=|y|=|z| \land (x \neq y \lor y \neq z)\}$ , que es el complemento de $\{www\}$ , con las palabras de longitud no $0$ mod $3$ eliminadas.

Deje $L' = \{uv : |u| \equiv_3 |v| \equiv_3 0 \land u_{2|u|/3} \neq v_{|v|/3}\}$ . Claramente, $L'$ es CFL, ya que puede adivinar una posición $p$ y considerar que $u$ termina $p/2$ después de eso. Mostramos que $L = L'$ .

• $L \subseteq L'$ : Let$w = xyz \in L$ . Suponga que hay una$p$ tal que$x_p \neq y_p$ . Luego escriba$u$ para los$3p/2$ primeros caracteres de$w$ , y$v$ para el resto. Naturalmente,$u_{2|u|/3} = x_p$ . Ahora que es$v_{|v|/3}$ ? Primero:

Por lo tanto, en $w$ , esta es la posición:

Si $y_p \neq z_p$ , entonces que $u$ sea el primero ${3\over2}(|w|/3 + p)$caracteres de$w$, de modo que$u_{2|u|/3}$es$y_p$; $v$es el resto de$w$. Entonces:

• $L' \subseteq L$ : Revertimos el proceso anterior. Sea$w = uv \in L'$ . Escribe$p = 2|u|/3$ . Entonces: $$p+|w|/3 = 2|u|/3+|uv|/3 = |u| + |v|/3.$$ Así$w_p = u_{2|u|/3} \neq v_{|v|/3} = w_{p + |w|/3}$ , y$w \in L$ (ya que si$w$ tiene la forma$xxx$ , debe contener que$w_p = w_{p+|w|/3}$ para todo$p$ ).

Esta es la forma en que pienso en resolver este problema, con un PDA. En mi opinión, es intuitivamente más claro.

Una palabra $x$ no tiene la forma $www$ iff tampoco (i) $|x| \not\equiv 0$ (mod 3), que es fácil de verificar, o (ii) hay algún símbolo de entrada $a$ que difiere del símbolo $b$ correspondiente que ocurre $|w|$posiciones más tarde.

Usamos el truco habitual de usar la pila para mantener un entero $t$ al tener un nuevo símbolo $Z$ "de la parte inferior de la pila" , almacenando el valor absoluto $|t|$como el número de contadores en la pila, y sgn ( $t$ ) por el estado del PDA. Por lo tanto, podemos aumentar o disminuir $t$ haciendo la operación apropiada.

El objetivo es usar el no determinismo para adivinar las posiciones de los dos símbolos que está comparando, y usar la pila para registrar $t := |x|-3d$ , donde $d$ es la distancia entre estos dos símbolos.

Logramos esto de la siguiente manera: incremente $t$ para cada símbolo visto hasta que se elija el primer símbolo adivinado $a$ , y registre $a$ en el estado. Para cada símbolo de entrada posterior, hasta que decida que ha visto $b$ , disminuya $t$ en $2$ ( $1$ para la longitud de entrada y $-3$ para la distancia). Adivina la posición del segundo símbolo $b$ y registra si $a \not= b$ . Continúe incrementando $t$ para los siguientes símbolos de entrada. Acepte si $t = 0$ (detectable por $Z$ en la parte superior) y$a \not= b$ .

Lo bueno de esto es que debe quedar completamente claro cómo extender esto a poderes arbitrarios.

Solo una perspectiva diferente ("orientada a la gramática") para demostrar que el complemento de $\{ w^k \}$ es CF para cualquier $k$ fija que use propiedades de cierre.

Primero tenga en cuenta que en el complemento de $\{ w^k \}$ siempre hay $i$ tal que $w_i \neq w_{i+1}$ . Nos centramos en $w_1 \neq w_2$ y comenzamos con una gramática CF simple que genera:

$L = \{\underbrace{a00...0}_{w_1} \; \underbrace{b00...0}_{w_2} ... \underbrace{000...0}_{w_k} \mid |w_i|=n \} = \{ a 0^{n-1} \, b 0^{n(k-1)-1} \}$

Por ejemplo, para $k = 3$ , tenemos $L = \{ a\,b\,0, a0\,b0\,00, a00\,b00\,000, ...\}$ ,$G_L = \{ S \to ab0 | aX00, X \to 0X00 | 0b0 \}$

Luego aplique cierre bajo homomorfismo inverso y unión :

Primer homomorfismo: $\varphi(1) \to a, \varphi(0) \to b, \varphi(1)\to 0, \varphi(0) \to 0$

Segundo homomorfismo: $\varphi'(0) \to a, \varphi'(1) \to b, \varphi'(1)\to 0, \varphi'(0) \to 0$

$L' = \varphi^{-1}(L) \cup \varphi'^{-1}(L)$ todavía está libre de contexto

Aplique el cierre debajo de los desplazamientos cíclicos a $L'$ para obtener el conjunto de cadenas de longitud $kn$ no de la forma $w^k$ :

$L'' = Shift(L') = \{ u \mid u \neq w^k \land |u| = kn \}$ .

Finalmente, agregue el conjunto regular de cadenas cuya longitud no es divisible por $k$ para obtener exactamente el complemento de $\{w^k\}$ :

$L'' \cup \{\{0,1\}^n\mid n \bmod k \neq 0\} = \{ u \mid u \neq w^k\}$