É o complemento de {www | …} Sem contexto?

É sabido que o complemento de é livre de contexto. Mas e o complemento de ?$\{ ww \mid w\in \Sigma^*\}$$\{ www \mid w\in \Sigma^*\}$

Ainda CFL eu acredito, com uma adaptação da prova clássica. Aqui está um esboço.

Considere $L = \{xyz : |x|=|y|=|z| \land (x \neq y \lor y \neq z)\}$ , que é o complemento de $\{www\}$ , com as palavras de comprimento não $0$ mod $3$ removidas.

Seja $L' = \{uv : |u| \equiv_3 |v| \equiv_3 0 \land u_{2|u|/3} \neq v_{|v|/3}\}$ . Claramente, $L'$ é CFL, já que você pode adivinhar uma posição $p$ considerar que $u$ termina $p/2$ depois disso. Mostramos que $L = L'$ .

• $L \subseteq L'$ : Let$w = xyz \in L$ . Suponha que exista um$p$ tal que$x_p \neq y_p$ . Em seguida, escreva$u$ para os$3p/2$ primeiros caracteres de$w$ , e$v$ para o resto. Naturalmente,$u_{2|u|/3} = x_p$ . Agora o que é$v_{|v|/3}$ ? Primeiro:

Portanto, em $w$ , esta é a posição:

Se $y_p \neq z_p$ , então $u$ seja o primeiro ${3\over2}(|w|/3 + p)$caracteres de$w$, de modo que$u_{2|u|/3}$é$y_p$; $v$é o resto de$w$. Então:

• $L' \subseteq L$ : Invertemos o processo anterior. Seja$w = uv \in L'$ . Escreva$p = 2|u|/3$ . Então: $$p+|w|/3 = 2|u|/3+|uv|/3 = |u| + |v|/3.$$ Assim,$w_p = u_{2|u|/3} \neq v_{|v|/3} = w_{p + |w|/3}$ e$w \in L$ (desde que$w$ tenha a forma$xxx$ , ele deve sustentar que$w_p = w_{p+|w|/3}$ para todos os$p$ ).

Aqui está a maneira como penso em resolver esse problema, com um PDA. Na minha opinião, é intuitivamente mais claro.

Uma palavra $x$ não tem a forma $www$ se (i) $|x| \not\equiv 0$ (mod 3), que é fácil de verificar, ou (ii) existe algum símbolo de entrada $a$ que difere do símbolo correspondente $b$ que ocorre $|w|$posições mais tarde.

Usamos o truque usual de usar a pilha para manter um número inteiro $t$ , tendo um novo símbolo "parte inferior da pilha" $Z$ , armazenando o valor absoluto $|t|$como o número de contadores na pilha e sgn ( $t$ ) pelo estado do PDA. Assim, podemos incrementar ou diminuir $t$ fazendo a operação apropriada.

O objetivo é usar o não determinismo para adivinhar as posições dos dois símbolos que você está comparando e usar a pilha para registrar $t := |x|-3d$ , onde $d$ é a distância entre esses dois símbolos.

Realizamos isso da seguinte maneira: incremente $t$ para cada símbolo visto até que o primeiro símbolo adivinhado $a$ seja escolhido e registre $a$ no estado. Para cada símbolo de entrada subsequente, até você decidir que viu $b$ , diminua $t$ em $2$ ( $1$ para o comprimento da entrada e $-3$ para a distância). Adivinhe a posição do segundo símbolo $b$ registre se $a \not= b$ . Continue incrementando $t$ para os símbolos de entrada subsequentes. Aceite se $t = 0$ (detectável por $Z$ na parte superior) e$a \not= b$ .

O bom disso é que deve ficar completamente claro como estender isso a poderes arbitrários.

Apenas uma perspectiva diferente ("orientada para a gramática") para provar que o complemento de $\{ w^k \}$ é CF para qualquer $k$ fixo usando propriedades de fechamento.

Primeira nota que no complemento de $\{ w^k \}$ sempre existe $i$ tal que $w_i \neq w_{i+1}$ . Focamos em $w_1 \neq w_2$ e começamos com uma gramática simples de CF que gera:

$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 exemplo, para $k = 3$ , temos $L = \{ a\,b\,0, a0\,b0\,00, a00\,b00\,000, ...\}$ ,$G_L = \{ S \to ab0 | aX00, X \to 0X00 | 0b0 \}$

Em seguida, aplique o fechamento sob homomorfismo inverso e união :

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

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

$L' = \varphi^{-1}(L) \cup \varphi'^{-1}(L)$ ainda está livre de contexto

Aplique o fechamento sob turnos cíclicos em $L'$ para obter o conjunto de cadeias de comprimento $kn$ não da forma $w^k$ :

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

Por fim, adicione o conjunto regular de strings cujo comprimento não é divisível por $k$ para obter exatamente o complemento de $\{w^k\}$ :

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