Apakah bahasa pasangan kata-kata dengan panjang yang sama yang jarak hamming-nya 2 atau lebih bebas dari konteks?

Apakah konteks bahasa berikut ini gratis?

L = {u x v y ∣ u, v, x, y \in {0, 1}^{+}, | u | = | v |, u \neq v, | x | = | y |, x \neq y}

$L = \{ uxvy \mid u,v,x,y \in \{ 0,1 \}^+, |u| = |v|, u \neq v, |x| = |y|, x \neq y\}$

Seperti yang ditunjukkan oleh sdcvvc, sebuah kata dalam bahasa ini juga dapat digambarkan sebagai gabungan dari dua kata dengan panjang yang sama dengan jarak hamming yang 2 atau lebih besar.

Saya pikir ini bukan konteks bebas tetapi saya kesulitan membuktikannya. Saya mencoba memotong bahasa ini dengan bahasa biasa (seperti misalnya) kemudian menggunakan lemma pemompaan dan \ atau homomorfisme tetapi saya selalu mendapatkan bahasa yang terlalu rumit untuk dikarakterisasi dan ditulis turun. $\ 0^*1^*0^*1^*$

formal-languages context-free pushdown-automata pumping-lemma open-problem Robert777
sumber

Apakah Anda mencoba memompa string ?

0^{u} 1^{x} 1^{u} 0^{x}

$0^u1^x1^u0^x$

Pål GD

Ya, tapi saya gagal memompa string ini keluar dari bahasa (itu tidak berarti bahwa itu tidak mungkin, hanya saja saya gagal melakukannya).

Robert777

@ PålGD, Anda mungkin perlu cara untuk "menandai" bagian-bagiannya, seperti

1^{u} 0 1^{x} 0 1^{u} 0 1^{x} 0

$1^u 0 1^x 0 1^u 0 1^x 0$

vonbrand

Bahasa ini dapat ditulis sebagai mana adalah jarak Hamming. Perhatikan bahwa jika kita mengganti 2 dengan 1, itu bebas konteks ( cs.stackexchange.com/questions/307 ) tetapi trik yang digunakan di sana tidak akan berfungsi. Secara pribadi saya bertaruh itu tidak bebas konteks.

{u v : | u | = | v |, d (u, v) \geq 2}

$\{uv:|u|=|v|,d(u,v) \geq 2\}$

d

$d$

sdcvvc

@ sdcvvc: Anda benar, satu partisi ke sehingga salah satu bit yang berbeda ada di dan yang lain di . Saya berdiri dikoreksi.

u

$u$

u^{'} x

$u'x$

u^{'}

$u'$

x

$x$

András Salamon

Jawaban:

Catatan [2019-07-30] Buktinya salah ... pertanyaannya lebih rumit daripada kedengarannya.

Setelah upaya yang gagal di sini adalah ide lain.

Jika kita memotong dengan bahasa reguler kita mendapatkan bahasa CF. $L$ $L_{reg} = 0^*10^*10^*10^*$

Mungkin kita dapat memiliki lebih banyak keberuntungan jika kita menggunakan (string dengan tepat 4 1s). $L_{reg}' = 0^*10^*10^*10^*10^*$

Misalkan , secara informal jika dapat dibagi menjadi dua bagian, sedemikian sehingga setengahnya mengandung persis atau kedua bagian mengandung dua tetapi posisi mereka tidak cocok. $L_1 = L \cap L_{reg}'$ $w \in L_1$ $\{0,1,3,4\}$ $1s$ $1$

Misalkan adalah CF dan biarkan menjadi tata bahasanya dalam bentuk normal Chomsky, dan biarkan $L_1$ $G$

w = u v = 0^{a} 1 0^{b} 1 0^{c} 1 0^{d} 1 0^{e} \in L_{1}

$w = uv = 0^a 1 0^b 1 0^c 1 0^d 1 0^e \in L_1$

Kami memiliki(panjang genap) dan $|u|=|v|$ $d(u,v) \geq 2$

Jika kita membatasi perhatian kita pada cara-cara di mana empat 1s dapat dihasilkan, kita memiliki tiga kasus yang ditunjukkan di bagian atas gambar 1. Bagian tengah gambar 1 menunjukkan kasus pertama (tetapi yang lainnya serupa) . $w$

masukkan deskripsi gambar di sini
Gambar 1 (gambar lengkap dapat diunduh di sini )

Jika kita memilih dan kita melihat bahwa nol antara dua pasang 1s harus dapat dipompa secara independen (titik merah pada gambar): khususnya, untuk cukup besar , kita mendapatkan duplikat nonterminal node pada subtree internal (simpul X pada gambar 2) atau pengulangan di jalur menuju yang pertama atau kedua 1 (simpul Y pada gambar 2). Perhatikan bahwa Gambar 2 sedikit disederhanakan: mungkin ada lebih banyak node nonterminal antara kedua , dan juga antara dua ( tetapi dengan yang hanya menghasilkan 0s di sebelah kanan yang pertama 1). $a=e, c=2a$ $b,d \gg a$ $b \gg a$ $X$ $Ys$ $Y\to ... \to Z_i \to ... Y$ $Z_i$

masukkan deskripsi gambar di sini
Gambar 2

Jadi kita dapat memperbaiki sembarang , lalu pilih cukup besar untuk mendapatkan simpul yang dapat dipompa secara independen pada urutan nol antara pertama dan kedua . Untuk urutan nol antara angka 1 ketiga dan keempat, kita dapat memilih . Tapi dapat dipompa secara independen sehingga ada dipompa substring , yaitu sedemikian sehingga dan . String yang kita dapatkan adalah: $a = e = k, c = 2a$ $b$ $1$ $d = b! +b$
$0^b$ $p \leq b$ $y$ $b = xyz, |y|=p, |x|\geq 0, |z|\geq 0$ $xy^iz = b!+b$

w^{'} = 0^{k} 1 0^{b! + b} 1 0^{2 k} 1 0^{b! + b} 1 0^{k}

$w' = 0^k 1 0^{b!+b} 1 0^{2k} 1 0^{b!+b} 1 0^k$

tapi kami tidak . Jadi bukan CF dan akhirnya bukan CF. $w' \notin L_1$ $L_1$ $L$

Jika buktinya benar (???) dapat diperluas ke setiap bahasa $L_k = \{ uv : |u|=|v|, d(u,v)\geq k\}, k\geq 2$

Vor
sumber

Saya khawatir hadiah akan kedaluwarsa sebelum kita benar-benar dapat memverifikasi bukti ini, jadi kecuali jika ada informasi drastis muncul dalam 4 jam ke depan, ini mendapat poin untuk menjadi upaya terbaik sejauh ini.

jmite

@ jamite: jangan khawatir ada kemungkinan besar bahwa itu adalah upaya yang salah seperti yang sebelumnya (yang berlangsung selama sekitar 30 menit sebelum menemukan kesalahan sepele) :-) :-)

Vor

Mengapa perbedaan kasus? Cabang-cabang dalam tata bahasa tidak memiliki hubungan dengan belahan kata. Tapi saya pikir itu tidak masalah; jika buktinya berhasil, perbedaan kasus ini tidak diperlukan. Melihat tata bahasa yang diasumsikan dan menggunakan bukti lemma pemompaan alih-alih lemma itu sendiri adalah trik yang bagus (kita harus melakukan ini lebih sering). Saya memiliki satu masalah (nyata): jika Anda memompa substring dari , Anda mendapatkan ; Saya tidak melihat bagaimana Anda bisa menjadi. Jangan berpikir itu akan merusak buktinya, tetapi periksa lebih baik. Juga, Anda mungkin ingin meluruskan beberapa notasi (dan kesalahan ketik).

0^{b}

$0^b$

0^{b + p (i - 1)}

$0^{b+p(i-1)}$

b + b!

$b+b!$

Raphael

@ Raphael: terima kasih atas komentarnya. Mungkin saya salah, tetapi jika Anda memilih sebagai target panjanglalu untuk setiap panjang pemompaan , string dapat didekomposisi dalam dan dapat dipompa ke, memang dalam contoh Anda p pasti membagi, jadi ada yang, tetapi panjang string asli adalah , sehingga total panjang yang dipompa adalah. Saya ingat dari beberapa latihan yang menggunakan lemma Ogden ... sekarang saya akan memeriksanya.

b + b!

$b+b!$

p

$p$

0^{b}

$0^b$

0^{x y z}, (| x y z | = b, | y | = p \leq b)

$0^{xyz}, (|xyz|=b, |y|=p \leq b)$

x y^{i} z = b + b!

$xy^iz = b + b!$

b!

$b!$

(i - 1)

$(i-1)$

p (i - 1) = b!

$p(i-1)=b!$

b

$b$

| x y^{(i - 1)} z | = b + b!

$|xy^{(i-1)}z| = b+b!$

Vor

@ Raphael: ... Saya tidak menemukan buktinya di mana pun tetapi hanya sebuah makalah oleh Zach Tomaszewski yang membuktikan bahwa komplemen adalah CF (lihat pertanyaan ), jadi mungkin ini adalah yang baru hasil (meskipun sederhana); dan teorema gaya-lemma pemompaan dapat diturunkan untuk bahasa dengan string yang berisi jumlah terbatas dari simbol tertentu dan substring dengan panjang arbiter di antara mereka.

L_{d u p} = {w w}

$L_{dup} = \{ ww \}$

Vor

Setelah 2 upaya gagal, yang dibantah oleh @Hendrik Jan (terima kasih), ini satu lagi, yang tidak lebih berhasil. @Vor menemukan contoh bahasa CF deterministik di mana konstruksi yang sama akan berlaku, jika benar. Ini memungkinkan pengidentifikasian kesalahan dalam penambatan string dalam penerapan lemma. Lemma itu sendiri tampaknya tidak bersalah. Ini jelas konstruksi yang terlalu sederhana. Lihat lebih detail di komentar. $y$

Bahasa tidak bebas konteks. $L = \{ uxvy \mid u,v,x,y \in \{ 0,1 \}^*\text \{ \epsilon \} \ ,\ \mid u \mid = \mid v \mid \ , \ u \not= v \ , \ \mid x \mid = \mid y \mid \ , \ x \not= y \ \}$

Sangat membantu untuk mengingat karakterisasi mana d adalah jarak Hamming, yang diusulkan oleh @sdcvvc. Yang perlu dipikirkan adalah 2 posisi yang dipilih di setiap setengah string sehingga simbol yang sesuai berbeda. $L= \{uv:|u|=|v|,d(u,v) \geq 2\}$

Maka Anda menganggap string sedemikian rupa sehingga dan adalah genap. Ini jelas dalam bahasa L, dengan memotong dan mana saja di antara keduanya 1. Kami ingin memompa string itu pada bagian pertama antara 1, sehingga akan menjadi yang tidak seharusnya dalam bahasa. $10^i10^j$ $i \lt j$ $i+j$ $u$ $x$ $10^j10^j$

Kami pertama-tama mencoba menggunakan lemma Ogden , yang seperti lemma pemompaan, tetapi berlaku untuk atau lebih simbol yang ditandai yang ditandai pada string, menjadi panjang pemompaan untuk simbol yang ditandai (tetapi lemma dapat memompa lebih banyak karena dapat memompa juga simbol tanpa tanda). Panjang pompa yang ditandai hanya bergantung pada bahasa. Upaya ini akan gagal, tetapi kegagalan akan menjadi petunjuk. $p$ $p$ $p$

Kami kemudian dapat memilih dan kami menandai simbol pada urutan pertama dari 0's. Kita tahu bahwa tidak ada satu pun dari 1 yang ada di pompa, karena bisa memompa sekali (eksponen 0) alih-alih memompa masuk. Dan memompa keluar 1 akan membuat kita keluar dari bahasa. $i=p$ $i$

Namun, kita bisa memompa di kedua sisi 1 kedua secepat atau bahkan lebih cepat di sisi kanan, sehingga 1 kedua tidak akan pernah melewati tengah tali. Juga lemma Ogden tidak memperbaiki batas atas untuk ukuran apa yang dipompa, sehingga tidak mungkin untuk mengatur pemompaan untuk mendapatkan 1 paling kanan tepat di tengah-tengah tali.

Kami menggunakan versi modifikasi dari lemma, di sini disebut Nash's Lemma, yang dapat mengatasi kesulitan ini.

Pertama-tama kita perlu definisi (mungkin memiliki nama lain dalam literatur, tapi saya tidak tahu yang mana - bantuan dipersilahkan). String dikatakan sebagai penghapusan string jika diperoleh dari dengan menghapus simbol dalam . Kami akan mencatat . $u$ $v$ $v$ $v$ $u \prec v$

Nash Lemma: Jika adalah bahasa bebas konteks, maka ada dua nomor dan sehingga untuk setiap string panjang setidaknya di , dan setiap cara “menandai” atau lebih posisi di , dapat ditulis sebagai dengan string , , , , , sedemikian rupa sehingga $L$ $p\gt0$ $q\gt 0$ $w$ $p$ $L$ $p$ $w$ $w$ $w=uxyzv$ $u$ $x$ $y$ $z$ $v$

$xz$ memiliki setidaknya satu posisi yang ditandai,
$xyz$ memiliki posisi paling banyak ditandai, dan $p$
ada 3 string , , sedemikian rupa y z
1. $\hat x \prec x$ , , , $\hat y \prec y$ $\hat z \prec z$
2. $1 \leq \mid \hat x \hat z \mid \leq q$ , , dan $1 \leq \mid \hat y \mid \leq q$
3. $ux^j\hat x^i\hat y\hat z^iz^jv$ ada di untuk setiap dan untuk setiap . $L$ $i \geq 0$ $j \geq 0$

Bukti : Mirip dengan bukti lemma Ogden, tetapi subpohon yang sesuai dengan string dan dipangkas sehingga mereka tidak mengandung jalur dengan dua kali non-terminal yang sama (kecuali untuk akar dari dua subpohon ini). Ini tentu membatasi ukuran string yang dihasilkan dan oleh konstan . String dan , untuk , terkait dengan versi pohon yang tidak ditandai, digunakan terutama dengan untuk menyederhanakan akuntansi ketika lemma diterapkan. $y$ $xz$ $\hat x\hat z$ $\hat y$ $q$ $x^j$ $z^j$ $j \geq 0$ $j=1$

Kami memodifikasi upaya bukti di atas dengan menandai simbol paling kiri 0, tetapi mereka diikuti oleh simbol 0 untuk memastikan bahwa kami memompa di bagian kiri string, di antara kedua 1 itu. Itu membuat total 0's antara 1's (sebenarnya akan cukup, karena 1 paling kanan tidak bisa di , yang akan memungkinkan untuk hanya menghapusnya). $p$ $2q$ $i = p + 2q$ $i = p + q$ $\hat z$

Yang tersisa adalah memilih sehingga kita dapat memompa tepat angka yang tepat dari 0 sehingga kedua urutannya sama. Namun sejauh ini, satu-satunya kendala pada adalah lebih besar dari . Dan kita juga tahu bahwa jumlah 0 yang dipompa pada setiap pemompaan adalah antara 1 dan q. Jadi biarkan menjadi produk dari integer pertama . Kami memilih . $j$ $j$ $i$ $h$ $q$ $j=i+h$

Oleh karena itu, karena kenaikan pemompaan - apa pun itu - ada di , ia membagi . Biarkan menjadi hasil bagi. Jika kita memompa tepat kali, kita mendapatkan string yang tidak ada dalam bahasa. Karenanya L tidak bebas konteks. $d$ $[1,q]$ $h$ $k$ $k$ $10^j10^j$

Saya pikir saya tidak akan pernah melihat
string yang indah seperti pohon.
Karena jika tidak memiliki parse,
senar tidak berarti apa-apa selain lelucon

babou
sumber

Namun, perhatikan bahwa lintasan di babak kedua membaca tumpukan secara terbalik. Itu tampaknya berarti bahwa kedua posisi berada di posisi yang sama di kedua bagian, tetapi sebaliknya?

Hendrik Jan

Anda benar ... Saya melakukan kesalahan ... sekarang saya tahu apa yang mengganggu saya di belakang kepala saya.

babou

Saya mengenali argumennya (karena saya tidak bisa membuatnya bekerja ketika saya mencoba sendiri).

Hendrik Jan

Haruskah saya meninggalkan jawaban yang salah ini? Entah bagaimana itu membantu, saya pikir, karena membuat masalah yang mirip dengan . Masalahnya adalah bahwa aturan situs tidak dimaksudkan untuk mendorong hasil yang salah untuk diskusi (maksud saya, saya tidak menikmati downvotes lebih dari orang lain).

a^{i} b^{j} c^{k} a^{i} b^{j} c^{k}

${a^ib^jc^ka^ib^jc^k}$

babou

@ HendrikJan Apakah saya melakukan kesalahan lagi? (BTW, terima kasih telah membuat diskusi)

babou

-1

oleh pertanyaan ini saya pikir bebas konteks dan dihasilkan oleh tata bahasa berikut $L$ $\qquad\begin{align} S &\to AXBY \mid BYAX \\ A &\to 0 \mid 0A0 \mid 0A1 \mid 1A0 \mid 1A1 \\ B &\to 1 \mid 0B0 \mid 0B1 \mid 1B0 \mid 1B1 \\ X &\to 0 \mid 0X0 \mid 0X1 \mid 1X0 \mid 1X1 \\ Y &\to 1 \mid 0Y0 \mid 0Y1 \mid 1Y0 \mid 1Y1 \\ \end{align}$

MK Dadsetani
sumber

Ini salah; Anda tidak dapat menjaga bahwa panjang AX sama dengan BY. Misalnya, tata bahasa Anda menghasilkan S -> AXBY -> A011 -> 0A1011 -> 001011 yang tidak dalam bahasa asli. Juga, simbol A dan X Anda menghasilkan bahasa yang sama, sama untuk B dan Y; mereka bisa digabung.

sdcvvc