Apakah pelengkap {ww | ...} bebas konteks?

Tetapkan bahasa sebagai . Dengan kata lain,$L$$L = \{a, b\}^* - \{ww\mid w \in \{a, b\}^*\}$$L$ berisi kata-kata yang tidak dapat diekspresikan karena beberapa kata diulang dua kali. Apakah$L$ bebas konteks atau tidak?

Saya sudah mencoba untuk berpotongan $L$ dengan $a^*b^*a^*b^*$ , tapi aku masih tidak bisa membuktikan apa-apa. Saya juga melihat teorema Parikh, tetapi itu tidak membantu.

Ini bebas konteks. Berikut tata bahasanya:

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$

menghasilkan kata-kata dengan panjang ganjil dengan a di tengah. Sama untuk B dan b .$A$$a$$B$$b$

Saya akan memberikan bukti bahwa tata bahasa ini benar. Biarkan (bahasa dalam pertanyaan).$L = \{a,b\}^* \setminus \{ww \mid w \in \{a,b\}^*\}$

Dalil. . Dengan kata lain, tata bahasa ini menghasilkan bahasa dalam pertanyaan.$L = L(S)$

Bukti. Hal ini tentu berlaku untuk semua kata-kata aneh-panjang, karena tata bahasa ini menghasilkan semua aneh-panjang kata-kata, seperti halnya . Jadi mari kita fokus pada kata-kata panjang.$L$

Misalkan memiliki panjang genap. Saya akan menunjukkan itu x ∈ L ( G ) . Secara khusus, saya menyatakan bahwa x dapat ditulis dalam bentuk x = u v , di mana kedua u dan v memiliki panjang aneh dan memiliki surat-surat pusat yang berbeda. Jadi x dapat diturunkan dari A B atau B A (sesuai dengan apakah huruf pusat u adalah a atau b ). Pembenaran klaim: Biarkan saya th surat $x \in L$$x \in L(G)$$x$$x=uv$$u$$v$$x$$AB$$BA$$u$$a$$b$$i$$x$dilambangkan , sehingga x = x 1 x 2 ⋯ x n . Maka karena x tidak dalam { w w ∣ w ∈ { a , b } n / 2 } , harus ada beberapa indeks i sedemikian rupa sehingga x i ≠ x i + n / 2 . Akibatnya kita dapat mengambil 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}$ danv= x 2 i ⋯ x n ; huruf pusatuakan menjadi x i , dan huruf pusatvakan menjadi x i + n / 2 , jadi dengan konstruksiu,vmemiliki huruf pusat yang berbeda.$u = x_1 \cdots x_{2i-1}$$v = x_{2i} \cdots x_n$$u$$x_i$$v$$x_{i+n/2}$$u,v$

Selanjutnya misalkan memiliki panjang genap. Saya akan menunjukkan bahwa kita harus memiliki x ∈ L . Jika x memiliki panjang genap, ia harus dapat diturunkan dari A B atau B A ; tanpa kehilangan umum, kira itu diturunkan dari A B , dan x = u v mana u adalah diturunkan dari A dan v adalah diturunkan dari B . Jika u , v memiliki panjang yang sama, maka kita harus memiliki u $x \in L(G)$$x \in L$$x$$AB$$BA$$AB$$x=uv$$u$$A$$v$$B$$u,v$ (karena mereka memiliki huruf pusat yang berbeda), jadi x ∉ { w w ∣ w ∈ { a , b } ∗ } . Jadi misalkan kamu , v memiliki panjang yang berbeda, katakanlah panjang ℓ dan n - ℓ masing-masing. Kemudian huruf pusatnya adalah u ( ℓ + 1 ) / 2 dan v ( n - ℓ + 1 ) / 2 . Fakta bahwa$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}$ memiliki huruf pusat yang berbeda berarti u ( ℓ + 1 ) / 2 ≠ v ( n - ℓ + 1 ) / 2 . Sejak x = u v , ini berarti bahwa x ( ℓ + 1 ) / 2 ≠ x ( n + ℓ + 1 ) / 2 . Jika kami mencoba mendekomposisi x sebagai x = w $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$ mana w , w ′ memiliki panjang yang sama, maka kita akan menemukan bahwa w ( ℓ + 1 ) / 2 = x ( ℓ + 1 ) / 2 ≠ x ( n + ℓ + 1 ) / 2 = w ′ ( ℓ + 1 ) / 2 , yaitu, w ≠ w ' , sehingga x ∉ { w $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'$ . Secara khusus, berikut bahwa x ∈ L .$x \notin \{ww \mid w \in \{a,b\}^*\}$$x \in L$

Bahasa ini bebas konteks, terbukti dalam makalah berikut:

Tomaszewski, Zach. "Tata Bahasa Bebas Konteks untuk String yang Diulang." Jurnal Informasi dan Ilmu Komputer , 2012 ( PDF ).

Tata bahasanya adalah sebagai berikut: