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

Sudah diketahui umum bahwa komplemen bebas konteks. Tapi bagaimana dengan komplemen ? $\{ ww \mid w\in \Sigma^*\}$ $\{ www \mid w\in \Sigma^*\}$

fl.formal-languages context-free domotorp
sumber

Saya telah menemukan bahwa ini adalah Teorema 4 dalam P. Dömösi, S. Horváth, M. Ito, L. Kászonyi, M. Katsura: Bahasa formal yang terdiri dari kata-kata primitif. link.springer.com/chapter/10.1007/3-540-57163-9_15

domotorp

Jawaban:

Masih CFL saya percaya, dengan adaptasi dari bukti klasik. Ini sketsa.

Pertimbangkan , yang merupakan komplemen dari , dengan kata-kata panjangnya tidak mod dihapus. $L = \{xyz : |x|=|y|=|z| \land (x \neq y \lor y \neq z)\}$ $\{www\}$ $0$ $3$

Biarkan . Jelas, adalah CFL, karena Anda dapat menebak posisi dan menganggap bahwa berakhir setelah itu. Kami menunjukkan bahwa . $L' = \{uv : |u| \equiv_3 |v| \equiv_3 0 \land u_{2|u|/3} \neq v_{|v|/3}\}$ $L'$ $p$ $u$ $p/2$ $L = L'$

$L \subseteq L'$ : Mari . Asumsikan ada sehingga . Kemudian tulis untuk karakter pertama , dan untuk sisanya. Secara alami, . Sekarang apa itu ? Pertama: $w = xyz \in L$ $p$ $x_p \neq y_p$ $u$ $3p/2$ $w$ $v$ $u_{2|u|/3} = x_p$ $v_{|v|/3}$

| v | / 3 = (| w | - 3 p / 2) / 3 = | w | / 3 - p / 2.

$|v|/3 = (|w| - 3p/2)/3 = |w|/3 - p/2.$

Karenanya, dalam , ini adalah posisi: atau, dengan kata lain, posisi dalam . Ini menunjukkan bahwa . $w$

| u | + | v | / 3 = 3 p / 2 + | w | / 3 - p / 2 = | w | / 3 + p,

$|u|+|v|/3 = 3p/2 + |w|/3 - p/2 = |w|/3 + p,$

p

$p$

y

$y$

u_{2 | u | / 3} = x_{p} \neq y_{p} = v_{| v | / 3}

$u_{2|u|/3} = x_p \neq y_p = v_{|v|/3}$

Jika , maka biarkan menjadi karakter pertama dari , sehingga adalah ; adalah sisa dari . Lalu: karenanya sama, . $y_p \neq z_p$ $u$ ${3\over2}(|w|/3 + p)$ $w$ $u_{2|u|/3}$ $y_p$ $v$ $w$

| u | + | v | / 3 = 2 | w | / 3 + p

$|u| + |v|/3 = 2|w|/3 + p$

v_{| v | / 3} = z_{p}

$v_{|v|/3} = z_p$

$L' \subseteq L$ : Kami membalikkan proses sebelumnya. Biarkan . Tulis . Kemudian: Jadi , dan (karena jika adalah dari bentuk , maka harus memegang bahwa untuk semua ). $w = uv \in L'$ $p = 2|u|/3$ $p + | w | / 3 = 2 | u | / 3 + | u v | / 3 = | u | + | v | / 3.$ $p+|w|/3 = 2|u|/3+|uv|/3 = |u| + |v|/3.$ $w_p = u_{2|u|/3} \neq v_{|v|/3} = w_{p + |w|/3}$ $w \in L$ $w$ $xxx$ $w_p = w_{p+|w|/3}$ $p$

Michaël Cadilhac
sumber

Wow, luar biasa! Saya tidak mengklaim bahwa saya telah mengikuti setiap detail argumen Anda, seperti saya tidak melihat apa yang Anda maksud dengan baris terakhir ('Untuk yang terakhir'), atau mengapa Anda tidak memisahkan kasing ketika

, tetapi solusi Anda akhirnya bekerja. Saya akan meringkas trik utama sebagai

. Trik yang sama juga berfungsi untuk melengkapi setiap

| w | / 3 < p / 2

$|w|/3<p/2$

3 a + 3 b = 2 a + (b - a) + 2 a + 2 b

$3a+3b=2a+(b-a)+2a+2b$

. Saya ingin tahu apakah

bebas konteks atau tidak.

L_{r} = {w^{r}}

$L_r=\{w^r\}$

L^{'} = {x y z : | x | = | y | = | z | \land (x \neq y)}

$L' = \{xyz : |x|=|y|=|z| \land (x \neq y)\}$

domotorp

@domotorp: Ceria! Baiklah, "bit terakhir" tidak perlu, terima kasih! Adapun "kasus ketika

", saya tidak yakin di mana Anda maksud itu. Apakah saya melewatkan sesuatu? Adapun

, saya bertanya-tanya melakukan hal yang sama "bukti" ini! Belum yakin :)

| w | / 3 < p / 2

$|w|/3 < p/2$

L^{'}

$L'$

Michaël Cadilhac

Oh, salahku,

selalu berlaku!

p / 2 \leq | w | / 3

$p/2\le |w|/3$

domotorp

Mungkin ini bukan masalah, tapi

bisa aneh, jadi Anda harus menangani kasus

Ketika

ganjil.

p

$p$

| u | = 3 p / 2 (?)

$|u| = 3p/2 (?)$

p

$p$

Marzio De Biasi

@MarzioDeBiasi: Ya, itulah mengapa ini adalah sketsa :-)

Michaël Cadilhac

Inilah cara saya berpikir untuk menyelesaikan masalah ini, dengan PDA. Menurut pendapat saya, secara intuitif lebih jelas.

$x$ $www$ $|x| \not\equiv 0$ $a$ $b$ $|w|$

Kami menggunakan trik biasa menggunakan stack untuk mempertahankan integer dengan memiliki simbol "bottom-of-stack" baru , menyimpan nilai absolutsebagai jumlah penghitung pada stack, dan sgn ( ) oleh keadaan PDA. Dengan demikian kita dapat menambah atau mengurangi dengan melakukan operasi yang sesuai. $t$ $Z$ $|t|$ $t$ $t$

Tujuannya adalah menggunakan nondeterminisme untuk menebak posisi dua simbol yang Anda bandingkan, dan menggunakan tumpukan untuk merekam , di mana adalah jarak antara kedua simbol ini. $t := |x|-3d$ $d$

Kami mencapai ini sebagai berikut: peningkatan untuk setiap simbol yang terlihat sampai simbol tebakan pertama dipilih, dan merekam di negara bagian. Untuk setiap simbol input selanjutnya, sampai Anda memutuskan Anda telah melihat , kurangi dengan ( untuk panjang input dan untuk jarak). Tebak posisi simbol kedua dan catat apakah . Terus menambah untuk simbol input selanjutnya. Terima jika (terdeteksi oleh di atas) dan . $t$ $a$ $a$ $b$ $t$ $2$ $1$ $-3$ $b$ $a \not= b$ $t$ $t = 0$ $Z$ $a \not= b$

Hal yang menyenangkan tentang ini adalah bahwa harus benar-benar jelas bagaimana memperluas ini ke kekuatan yang sewenang-wenang.

Jeffrey Shallit
sumber

Memang sangat rapi!

domotorp

Ah, memang jauh lebih baik :-)

Michaël Cadilhac

Perspektif yang berbeda ("berorientasi tata bahasa") untuk membuktikan bahwa komplemen dari adalah CF untuk setiap fix menggunakan properti closure. $\{ w^k \}$ $k$

Pertama perhatikan bahwa dalam komplemen selalu ada sedemikian rupa sehingga . Kami fokus pada dan mulai dengan tata bahasa CF sederhana yang menghasilkan: $\{ w^k \}$ $i$ $w_i \neq w_{i+1}$ $w_1 \neq w_2$

$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} \}$

Misalnya untuk , kita memiliki , $k = 3$ $L = \{ a\,b\,0, a0\,b0\,00, a00\,b00\,000, ...\}$ $G_L = \{ S \to ab0 | aX00, X \to 0X00 | 0b0 \}$

Kemudian menerapkan penutupan di bawah homomorfisme terbalik , dan penyatuan :

Homomorfisme pertama: $\varphi(1) \to a, \varphi(0) \to b, \varphi(1)\to 0, \varphi(0) \to 0$

Homomorfisme kedua: $\varphi'(0) \to a, \varphi'(1) \to b, \varphi'(1)\to 0, \varphi'(0) \to 0$

$L' = \varphi^{-1}(L) \cup \varphi'^{-1}(L)$ masih bebas konteks

Terapkan penutupan di bawah shift siklik ke untuk mendapatkan set string panjang bukan dari bentuk : $L'$ $kn$ $w^k$

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

Terakhir, tambahkan rangkaian string reguler yang panjangnya tidak dapat dibagi oleh untuk mendapatkan pelengkap : $k$ $\{w^k\}$

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

Marzio De Biasi
sumber