Jest uzupełnieniem {ww | …} Bez kontekstu?

Zdefiniuj język jako . Innymi słowy, zawiera słowa, których nie można wyrazić jako jakieś słowo powtórzone dwukrotnie. Czy bezkontekstowy czy nie?$L$$L = \{a, b\}^* - \{ww\mid w \in \{a, b\}^*\}$$L$$L$

Próbowałem przeciąć z , ale nadal nie mogę niczego udowodnić. Spojrzałem również na twierdzenie Parikha, ale to nie pomaga.$L$$a^*b^*a^*b^*$

Jest bezkontekstowy. Oto gramatyka:

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

$A$Generuje słowa długości nieparzystej z w centrum. To samo dla i .$a$$B$$b$

Przedstawię dowód, że ta gramatyka jest poprawna. Niech (język w pytaniu).$L = \{a,b\}^* \setminus \{ww \mid w \in \{a,b\}^*\}$

Twierdzenie. . Innymi słowy, ta gramatyka generuje język w pytaniu.$L = L(S)$

Dowód. To z pewnością odnosi się do wszystkich dziwne długości słów, ponieważ to gramatyka generuje wszystkie nieparzystych długości słowa, podobnie jak . Skupmy się więc na słowach o równej długości.$L$

Załóżmy, że ma parzystą długość. Pokażę, że . W szczególności twierdzę, że można zapisać w postaci , gdzie zarówno jak i mają nieparzystą długość i różne litery środkowe. Zatem może być pochodzenia lub (w zależności od tego, czy jest centralny litera jest lub ). Uzasadnienie roszczenia: Niech ta litera będzie oznaczona , tak aby . Potem od$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$nie ma w , musi istnieć jakiś indeks taki, że . W związku z tym możemy wziąć i ; środkowa litera będzie , a środkowa litera będzie , więc ze względu na budowę mają różne środkowe litery.$\{ww \mid w \in \{a,b\}^{n/2}\}$$i$$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$

Następnie załóżmy, że ma parzystą długość. Pokażę, że musimy mieć . Jeśli ma parzystą długość, musi pochodzić z lub ; bez utraty ogólności, załóżmy, że nie wypływa , a , gdzie jest pochodzących z i można otrzymać drogą . Jeśli mają te same długości, to musimy mieć (ponieważ mają różne środkowe litery), więc . Załóżmy więc,$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$mają różne długości, powiedzmy odpowiednio długość i . Następnie ich środkowymi literami są i . Fakt, że mają różne środkowe litery, oznacza, że . Ponieważ , oznacza to, że . Jeśli spróbujemy dekomponować jako gdzie mają tę samą długość, wówczas odkryjemy, że , tj. , więc$\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$$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\}^*\}$ . W szczególności, wynika to, że .$x \in L$

Ten język jest pozbawiony kontekstu, co zostało udowodnione w następującym artykule:

Tomaszewski, Zach. „Gramatyka bezkontekstowa dla powtarzającego się łańcucha”. Journal of Information and Computer Science , 2012 ( PDF ).

Gramatyka jest następująca: