Apa kompleksitas keadaan bahasa salinan?

Biarkan nomor diberikan. Pertimbangkan bahasa berikut $n$ . $L_n = \{ \; ww \; \vert \; w \in \{0,1\}^{n} \; \}$

Dengan kata lain, adalah himpunan string salinan dengan panjang . $L_n$ $2n$

Pertimbangkan fungsi kompleksitas keadaan berikut sehingga adalah jumlah negara di Automata Pushdown terkecil yang mengenali . $s$ $s(n)$ $L_n$

Pertanyaan: Bisakah Anda secara resmi membuktikan batas bawah yang berarti untuk ? $s(n)$

Dugaan Saya: . $s(n) = 2^{\Theta(n)}$

Upperbound yang dikenal: . $s(n) \leq \mathrm{poly}(n) \cdot 2^{\frac{n}{2}}$

Aturan:

(1) Alfabet tumpukan harus biner.

(2) Pita input satu arah dan tidak dapat berhenti pada karakter input apa pun.

fl.formal-languages automata-theory grammars context-free Michael Wehar
sumber

Saat ini saya tidak memiliki batas bawah yang berarti. Menurut saya, Anda mungkin dapat membuktikan batas bawah untuk jumlah variabel yang Anda butuhkan untuk CFG yang mengenali bahasa tersebut. Meskipun, saya bahkan tidak sepenuhnya yakin akan hal ini.

Michael Wehar

Intuisi saya adalah bahwa ketika Anda mendorong karakter dari tape input ke stack, Anda mengalami masalah. Jika Anda ingin mengambil bit ini nanti, Anda harus membuang semua bit yang Anda dorong di atasnya. Dengan kata lain, tampaknya tumpukan itu tidak membantu Anda karena semakin Anda mendorongnya, semakin banyak Anda terpaksa melupakannya nanti.

Michael Wehar

Catatan: Untuk DFA (automata tanpa tumpukan), Anda dapat membuktikan kompleksitas keadaan eksponensial lebih rendah.

Michael Wehar

Bisakah Anda menunjukkan batas bawah yang wajar untuk masalah sederhana

{0^{k} 1^{l} 0^{k} 1^{l}}

$\{0^k1^l0^k1^l\}$

András Salamon

Batas atas yang lebih tepat tampaknya

menyatakan.

(n + 3) 2^{n / 2}

$(n+3)2^{n/2}$

András Salamon

Jawaban:

Teknik yang dijelaskan oleh Yuval:

Apakah ada CFG ukuran polinomial yang menjelaskan bahasa terbatas ini?

(Anda juga dapat membaca: Batas bawah pada ukuran CFG untuk bahasa terbatas tertentu )

memungkinkan untuk menunjukkan dengan sangat mudah batas bawah eksponensial untuk CFG. Biarkan tata bahasa di Chomsky Normal Form untuk . Untuk setiap kata terdapat setidaknya satu non-terminal menerima subword dari memiliki panjang antara dan . Biarkan menjadi posisi dalam $G$ $L_n$ $w\in \{0,1\}^n$ $A(w)$ $s(w)$ $ww$ $n/2$ $n$ $p(w)$ $ww$ di mana subword ini terjadi. Setidaknya ada bit yang umum untuk semua kata sehingga dan . Akibatnya, paling tidak ada kata yang memiliki dan . Karenanya setidaknya ada $n/2$ $w,w'$ $A(w)=A(w')$ $p(w)=p(w')$ $2^{n/2}$ $A(w)$ $p(w)$ bukan terminal. $2^{\Theta(n)}$

Selain itu, PDA dapat dikonversi menjadi CFG di CNF, dengan ukuran polinomial sehingga ini juga memberikan terikat pada kompleksitas keadaan . $2^{\Theta(n)}$ $L_n$

Joseph Stack
sumber

Luar biasa, terima kasih lagi! Saya melihat sekarang dan akan memikirkannya untuk mengonfirmasi. :)

Michael Wehar

Benar lagi: mengubah panjang dari

memperkenalkan masalah lain. Saya harus memperbaiki argumen dengan cara yang mirip dengan Yuval (menghitung tumpang tindih). Sekarang saya percaya itu benar, akhirnya. Saya mengedit jawabannya dan menghapus komentar saya

[n, 2 n]

$[n,2n]$

[n / 2, n]

$[n/2,n]$

Joseph Stack

Seandainya itu membantu orang lain: perhatikan bahwa sekali

telah dipilih,

hanya dapat menghasilkan satu kata kunci

yang dimulai pada posisi

. Jadi ini sebenarnya menunjukkan bahwa CNF-CFG yang benar untuk bahasa ini harus memiliki banyak nonterminal yang masing-masing menghasilkan subword panjang yang tunggal.

(A (w), p (w))

$(A(w),p(w))$

A (w)

$A(w)$

w w

$ww$

p (w)

$p(w)$

András Salamon

Lihat juga Teorema 7 di makalah saya: cs.toronto.edu/~yuvalf/CFG-LB.pdf .

Yuval Filmus

@YuvalFilmus Perlu juga dicatat bahwa Andras menghabiskan sedikit waktu mencoba untuk mendapatkan batas atas dan bawah yang cocok. Teman saya, Pepe, dan saya mendefinisikan kelas umum bahasa terbatas dan menerapkan tekniknya pada mereka. Kami tidak pernah menulis apa pun. Jika Anda memiliki masalah terkait, kami akan berkolaborasi lebih dari cukup. Terima kasih lagi.

Michael Wehar