Apakah {ww '| HamDist (w, w ')> 1} bebas konteks?

Setelah membaca pertanyaan terakhir "Apakah komplemen bebas konteks?" $\{ www \mid ...\}$ ; Saya ingat masalah yang sama yang tidak bisa saya tolak:

Apakah konteks gratis? $L = \{ ww' \mid w,w' \in \{0,1\}^* \land |w|=|w'| \land HamDist(w,w')>1 \}$

Di sini kita mensyaratkan bahwa dua string berbeda setidaknya dalam dua posisi (jarak Hamming harus lebih besar dari ). $1$

Ini bebas konteks jika kita mengharuskan $HamDist(w,w')\geq 1$ (yaitu dua string harus berbeda).

Saya menduga bahwa bahasa tersebut tidak bebas konteks: jika kita memotongnya dengan $0^*10^*10^*10^*$ biasa kita mendapatkan kasus di mana PDA harus "mengingat" dua posisi dalam urutan terbalik setelah mencapai setengah dari string.

Pembaruan: jika kita memotong $L$ dengan $R = \{ 0^*10^*10^*10^* \}$ kita mendapatkan bahasa bebas konteks seperti yang ditunjukkan oleh domotorp dalam jawabannya; $L \cap R'$ sedikit lebih kompleks dengan $R' = \{ 0^*10^*10^*10^*10^*10^* \}$ (satu lagi $1$ untuk "melacak") masih menyarankan bahwa $L$ seharusnya tidak bebas konteks.

fl.formal-languages context-free Marzio De Biasi
sumber

L \cap R^{'}

$L\cap R'$ sebenarnya lebih mudah, karena itu persis kata-kata yang bukan dari (berpotongan dengan ).

w w

$ww$

R^{'}

$R'$

domotorp

@domotorp: benar! diubah menjadi ganjil detik (kecuali jawaban Anda dapat disesuaikan juga dengan , untuk ganjil tetap )

1

$1$

{(0^{*} 1 0^{*})^{k}}

$\{ (0^* 1 0^*)^k \}$

k

$k$

Marzio De Biasi

Satu komentar terakhir: Ini tidak membantu untuk memulai dengan memimpin nol, karena bahasa bebas konteks ditutup untuk semua jenis perubahan siklik. Anda bisa mendorong mereka ke tumpukan, tandai yang terakhir dengan simbol khusus, lakukan sisa algoritma dengan berpura-pura bahwa tumpukan dimulai di sana, dan pada akhirnya kosongkan. (Ini menggunakan transisi , tapi itu juga mudah bahwa PDA seperti itu setara dengan yang tanpa.)

ϵ

$\epsilon$

domotorp

mungkin lebih mudah untuk memikirkan alfabet {0,1,2} dan mempertimbangkan string dengan tepat dua 1 dan dua 2. Ini bukan dalam bahasa Anda jika jarak antara 1s dan jarak antara 2s keduanya n.

Kaveh

Jawaban:

Persimpangan dengan kata panjang genap bebas konteks, karena PDA dapat mengingat dua posisi, dengan cara tertentu. Bagaimanapun, mari kita lihat apa bahasa ini. Komplemennya adalah . Oleh karena itu, . Kita dapat menulis ulang ini sebagai . $R=\{0^*10^*10^*10^*\mid$ $\}$ $L$ $R\setminus L=\{0^a10^b10^c10^d\mid b=n/2 \vee c=n/2 \vee a+d=n/2\}$ $L=\{0^a10^b10^c10^d\mid b\ne n/2 \wedge c\ne n/2 \wedge a+d\ne n/2\}$ $L=\{0^a10^b10^c10^d\mid b> n/2 \vee c> n/2 \vee a+d> n/2 \vee b,c,a+d<n/2\}$

kasus pertama dapat dengan mudah diverifikasi, dan begitu juga yang keempat. $3$

$b>n/2$ : Mulai masukkan ke dalam tumpukan sampai yang pertama, kemudian mulai muncul dari tumpukan sampai kosong. Setelah kosong, mulai lagi masukkan ke dalam tumpukan sampai kita mencapai yang kedua.

$c>n/2$ : Sama.

$a+d>n/2$ : Mulai masukkan ke dalam tumpukan sampai yang pertama, kemudian mulai muncul dari tumpukan sampai kosong. Setelah kosong, mulai lagi masukkan ke stack sampai kita mencapai yang ketiga.

$b,c,a+d<n/2$ : Mulai masukkan ke dalam tumpukan sampai yang pertama, kemudian mulai muncul dari tumpukan sampai tidak kosong. Setelah kosong, mulai lagi masukkan ke dalam tumpukan sampai kita mencapai (tebak non-deterministik, di suatu tempat antara kedua dan ketiga 1). Sejak saat itu pop stack. $a+n/2$

domotorp
sumber

Terima kasih domotorp, saya membaca ide Anda; Saya pikir adalah (dua 1s di bagian kiri) satukan kebalikannya (dua 1s di bagian kanan). Jadi bagaimana Anda mendapatkan ?

R ∖ L

$R \setminus L$

{0^{a} 1 0^{b} 1 0^{c^{'}} 0^{c^{″}} 1 0^{d} ∣ (n / 2 = a + b + c^{'} = c^{″} + d + 1) \land [(a = c^{″}) \lor (c^{'} = d)}

$\{ 0^a 1 0^b 1 0^{c'} 0^{c''} 1 0^d \mid \ (n/2=a+b+c'=c''+d+1) \land [(a= c'')\lor (c' = d) \}$

b = n / 2 \lor c = n / 2 \lor a + d = n / 2

$b=n/2 \vee c=n/2 \vee a+d=n/2$

Marzio De Biasi

R \subset L

$R\subset L$ adalah bahwa HamDist paling banyak . Ini terjadi persis jika dua dari tiga pertandingan 1, yaitu, satu berada di posisi yang sama di babak pertama, seperti yang lain di babak kedua. Jika kedua 1 ini adalah yang pertama dan kedua, maka kita mendapatkan , jika mereka adalah yang kedua dan ketiga, kita mendapatkan , dan jika mereka adalah yang pertama dan ketiga, kita mendapatkan , atau ekuivalen, (di mana saya curang sedikit dengan beberapa konstanta 's).

1

$1$

b = n / 2

$b=n/2$

c = n / 2

$c=n/2$

b + c = n / 2

$b+c=n/2$

a + d = n / 2

$a+d=n/2$

\pm 1

$\pm 1$

domotorp

Apakah ini menjawab pertanyaan lengkap?

Michaël Cadilhac

@domotorp: ok saya mengerti, terima kasih! Keraguan lain: dari (yang tidak masalah) Anda menulis tetapi, apakah ini setara dengan: ? ( dihilangkan)

L \cap R = {. . . b \neq n / 2 \land c \neq n / 2...}

$L \cap R = \{...b \neq n/2 \land c \neq n/2...\}$

L \cap R = {. . . b > n / 2 \lor c > n / 2 \lor b, c < n / 2}

$L \cap R = \{ ...b > n/2 \lor c > n/2 \lor b,c < n/2 \}$

L \cap R = {. . . (b < n / 2 \lor b > n / 2) \land (c < n / 2 \lor c > n / 2)}

$L \cap R = \{... (b < n/2 \lor b >n/2) \land (c < n/2 \lor c >n/2)\}$

a + d

$a+d$

Marzio De Biasi

@Michael: No.

$~$

domotorp