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

Defina o idioma como . Em outras palavras, contém as palavras que não podem ser expressas como algumas palavras repetidas duas vezes. é livre de contexto ou não?$L$$L = \{a, b\}^* - \{ww\mid w \in \{a, b\}^*\}$$L$$L$

Tentei cruzar com , mas ainda não posso provar nada. Eu também olhei para o teorema de Parikh, mas isso não ajuda.$L$$a^*b^*a^*b^*$

É livre de contexto. Aqui está a gramática:

A → a | a A uma | a A b | b A b | b A a B → b | a B a | a B b | b B b | b B $S \to A | B|AB|BA$
$A \to a|aAa|aAb|bAb|bAa$
$B \to b|aBa|aBb|bBb|bBa$

a B $A$ gera palavras de comprimento ímpar com no centro. O mesmo para e .$a$$B$$b$

Vou apresentar uma prova de que esta gramática está correta. Deixe (o idioma da pergunta).$L = \{a,b\}^* \setminus \{ww \mid w \in \{a,b\}^*\}$

Teorema. . Em outras palavras, essa gramática gera o idioma na pergunta.$L = L(S)$

Prova. Isso certamente vale para todas as palavras ímpar de comprimento, uma vez que esta gramática gera todos os ímpares comprimentos de palavras, como faz . Então, vamos nos concentrar em palavras pares.$L$

Suponha que tenha comprimento uniforme. Vou mostrar que . Em particular, afirmo que pode ser escrito na forma , onde e têm um comprimento ímpar e têm letras centrais diferentes. Assim, pode ser derivado de ou (conforme a letra central de é ou ). Justificação de reivindicação: Deixe o th carta de ser denotado , de modo que . Então desde quex ∈ G ( G ) x x = u v u v x A B B A u uma b i x x i x = x 1 x 2 ⋯ x n x { w w | w ∈ { um , b } n / 2 } i x i ≠ x i + $x \in L$$x \in L(G)$$x$$x=uv$$u$$v$$x$$AB$$BA$$u$$a$$b$$i$$x$$x_i$$x = x_1 x_2 \cdots x_n$$x$não está em , deve existir algum índice tal que . Conseqüentemente, podemos pegar e ; a letra central de será e a letra central de será ; portanto, pela construção terá letras centrais diferentes.$\{ww \mid w \in \{a,b\}^{n/2}\}$$i$ u=x1⋯x 2 i - 1 v=x 2 i ⋯xnuxivx i + n / 2 u,$x_i \ne x_{i+n/2}$$u = x_1 \cdots x_{2i-1}$$v = x_{2i} \cdots x_n$$u$$x_i$$v$$x_{i+n/2}$$u,v$

Em seguida, suponha que tenha comprimento uniforme. Vou mostrar que devemos ter . Se tiver um comprimento uniforme, deverá ser derivado de ou ; sem perda de generalidade, suponhamos que é derivável a partir de , e onde é derivável de e é derivável a partir de . Se tem o mesmo comprimento, então devemos ter (uma vez que possuem letras centrais diferentes), de modo que . Então, suponha quex ∈ L x A B B A A B x = u v u A v B u , v u ≠ v x ∉ { w w | w ∈ { um , b } * } u , $x \in L(G)$$x \in L$$x$$AB$$BA$$AB$$x=uv$$u$$A$$v$$B$$u,v$$u\ne v$$x \notin \{ww \mid w \in \{a,b\}^*\}$$u,v$têm comprimentos diferentes, digamos comprimento e respectivamente. Então, suas letras centrais são e . O fato de que possui letras centrais diferentes significa que . Como , isso significa que . Se tentarmos decompor como onde tem o mesmo comprimento, descobriremos que , ou seja, , entãon - ℓ u ( ℓ + 1 ) / 2 v ( n - ℓ + 1 ) / 2 u , v u ( ℓ + 1 ) / 2 ≠ v ( n - ℓ + 1 ) / 2 x = u v x ( ℓ + 1 ) / 2 ≠ x ( n $\ell$$n-\ell$$u_{(\ell+1)/2}$$v_{(n-\ell+1)/2}$$u,v$$u_{(\ell+1)/2} \ne v_{(n-\ell+1)/2}$$x=uv$ xx=w w ′ w, w ′ w ( ℓ + 1 ) / 2 = x ( ℓ + 1 ) / 2 ≠ x ( n + ℓ + 1 ) / 2 = w ′ ( ℓ + 1 ) / 2 w≠ w ′ x∉$x_{(\ell+1)/2} \ne x_{(n+\ell+1)/2}$$x$$x=ww'$$w,w'$$w_{(\ell+1)/2} = x_{(\ell+1)/2} \ne x_{(n+\ell+1)/2} = w'_{(\ell+1)/2}$$w\ne w'$$x \notin \{ww \mid w \in \{a,b\}^*\}$ . Em particular, segue-se que .$x \in L$

Essa linguagem é livre de contexto, foi comprovada no seguinte artigo:

Tomaszewski, Zach. "Uma gramática livre de contexto para uma sequência repetida." Revista de Informação e Ciência da Computação , 2012 ( PDF ).

A gramática é a seguinte: