Est le complément de {ww | …} Sans contexte?

Définissez la langue $L$ comme $L = \{a, b\}^* - \{ww\mid w \in \{a, b\}^*\}$ . En d'autres termes, $L$ contient les mots qui ne peuvent pas être exprimés comme un mot répété deux fois. L est $L$-il sans contexte ou non?

J'ai essayé de croiser L avec un ∗ b ∗ a ∗ b ∗ , mais je ne peux toujours rien prouver. J'ai également regardé le théorème de Parikh, mais cela n'aide pas.$L$$a^*b^*a^*b^*$

C'est sans contexte. Voici la grammaire:

S → A | B | A B | B A A → a | a A a | 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 génère des mots de longueur impaire avec un au centre. Idem pour B et b .$A$$a$$B$$b$

Je vais présenter une preuve que cette grammaire est correcte. Soit L = { a , b } ∗ ∖ { w w ∣ w ∈ { a , b } ∗ } (la langue de la question).$L = \{a,b\}^* \setminus \{ww \mid w \in \{a,b\}^*\}$

Théorème. L = L ( S ) . En d'autres termes, cette grammaire génère la langue de la question.$L = L(S)$

Preuve. Cela vaut certainement pour tous les mots impairs, car cette grammaire génère tous les mots bizarres longueurs, tout comme L . Concentrons-nous donc sur les mots de longueur égale.$L$

Supposons que x ∈ L ait une longueur paire. Je vais montrer que x ∈ L ( G ) . En particulier, je prétends que x peut être écrit sous la forme x = u v , où u et v ont une longueur impaire et des lettres centrales différentes. Ainsi, x peut être dérivé de A B ou B A (selon que la lettre centrale de u est a ou b ). Justification de la réclamation: Soit la i ème lettre de $x \in L$$x \in L(G)$$x$$x=uv$$u$$v$$x$$AB$$BA$$u$$a$$b$$i$$x$soit notée x i , de sorte que x = x 1 x 2 ⋯ x n . Alors comme x n'est pas dans { w w ∣ w ∈ { a , b } n / 2 } , il doit exister un indice i tel que x i ≠ x i + n / 2 . Par conséquent , nous pouvons prendre u = x 1 ⋯ x 2 i $x_i$$x = x_1 x_2 \cdots x_n$$x$$\{ww \mid w \in \{a,b\}^{n/2}\}$$i$$x_i \ne x_{i+n/2}$1 etv= x 2 i ⋯ x n ; la lettre centrale deusera x i , et la lettre centrale devsera x i + n / 2 , donc par constructionu,vaura différentes lettres centrales.$u = x_1 \cdots x_{2i-1}$$v = x_{2i} \cdots x_n$$u$$x_i$$v$$x_{i+n/2}$$u,v$

Supposons ensuite que x ∈ L ( G ) ait une longueur paire. Je vais montrer que nous devons avoir x ∈ L . Si x a une longueur paire, elle doit être dérivée de A B ou B A ; sans perte de généralité, on suppose qu'il peut être dérivé d' un B , et x = u v où u est dérivable à partir de A et v est dérivable à partir de B . Si u , v ont les mêmes longueurs, alors nous devons avoir u $x \in L(G)$$x \in L$$x$$AB$$BA$$AB$$x=uv$$u$$A$$v$$B$$u,v$v (car ils ont des lettres centrales différentes), donc x ∉ { w w ∣ w ∈ { a , b } ∗ } . Supposons donc que u , v aient des longueurs différentes, disons respectivement longueur ℓ et n - ℓ . Alors leurs lettres centrales sont u ( ℓ + 1 ) / 2 et v ( n - ℓ + 1 ) / 2 . Le fait que$u\ne v$$x \notin \{ww \mid w \in \{a,b\}^*\}$$u,v$$\ell$$n-\ell$$u_{(\ell+1)/2}$$v_{(n-\ell+1)/2}$$u,v$ have different central letters means that $u_{(\ell+1)/2} \ne v_{(n-\ell+1)/2}$. Since $x=uv$, this means that $x_{(\ell+1)/2} \ne x_{(n+\ell+1)/2}$. If we attempt to decompose $x$ as $x=ww'$ where $w,w'$ have the same length, then we'll discover that $w_{(\ell+1)/2} = x_{(\ell+1)/2} \ne x_{(n+\ell+1)/2} = w'_{(\ell+1)/2}$, i.e., $w\ne w'$, so $x \notin \{ww \mid w \in \{a,b\}^*\}$. In particular, it follows that $x \in L$.

This language is context free it was proved in the following paper:

Tomaszewski, Zach. "A Context-Free Grammar for a Repeated String." Journal of Information and Computer Science, 2012 (PDF).

The grammar is as follows: