Keteraturan tengah kata yang tepat dari bahasa biasa

8

Biarkan menjadi bahasa biasa. Apakah bahasa teratur? $L$
$L_2 = \{y : \exists x,z\ \ s.t.|x|=|z|\ and\ xyz \in L \}$

Saya tahu ini sangat mirip dengan pertanyaan di sini , tetapi yang menarik adalah bahwa itu bukan substring sederhana dari sebuah kata dalam bahasa biasa, melainkan "tengah tepat" - kita harus menghitung awalan dan panjang akhiran.

Karena itu, saya menganggap itu tidak biasa, tetapi saya tidak dapat menemukan cara untuk membuktikannya. Saya juga tidak bisa memikirkan cara untuk memodifikasi NFA untuk menerima . $L$ $L_2$

formal-languages regular-languages closure-properties Tomer
sumber

"tepat tengah" tampaknya menyarankan? Ngomong-ngomong, itu juga biasa!

| x | = | y | = | z |

$|x|=|y|=|z|$

Hendrik

Sudahkah Anda mencoba barang dari pertanyaan referensi kami ?

Raphael

6

Petunjuk: Pertimbangkan beberapa DFA untuk . Untuk setiap , misalkan adalah himpunan status sehingga ada beberapa kata panjang yang mengarahkan DFA dari keadaan awal ke . Biarkan menjadi himpunan status sehingga ada beberapa kata dengan panjang yang mengarahkan DFA dari ke status penerima. Akhirnya, untuk dua status , misalkan menjadi kumpulan kata (biasa) yang mengarahkan DFA dari ke . Kita punya $L$ $n \geq 0$ $A_n$ $s$ $n$ $s$ $B_n$ $t$ $n$ $t$ $s,t$ $R_{s,t}$ $s$ $t$

L_{2} = ⋃_{n \geq 0} ⋃_{\begin{matrix} s \in A_{n} \\ t \in B_{n} \end{matrix}} R_{s, t} .

$L_2 = \bigcup_{n \geq 0} \bigcup_{\substack{s \in A_n \\ t \in B_n}} R_{s,t}.$ Karena hanya ada banyak kemungkinan untuk , serikat sebenarnya terbatas, dan sangat teratur.

s, t

$s,t$

Yuval Filmus
sumber

3

Misalkan menjadi DFA untuk . Tanpa kehilangan umum, menganggap . Kami membangun ε-NFA untuk dengan cara berikut: $D = (Q, Σ, δ, q_0, F)$ $L$ $q_S, q_F \notin Q$ $N = (Q ∪ \{q_S, q_F\}, Σ, Δ, q_S, \{q_F\})$ $L_2$

Cari setiap jalur di dari untuk setiap . Untuk setiap jalur seperti itu buat jalur untuk (yaitu menyusun semua "bagian tengah" dari jalan). Ini dapat dilakukan secara efektif. Bangun dengan menggabungkan semua jalur ini, bersama dengan: $D$ $q_0$ $f ∈ F$ $p_k: q_0 = q_{k,0} \xrightarrow{α_{k,1}} q_{k,1} \xrightarrow{α_{k,2}} … \xrightarrow{α_{k,i}} q_{k,i} \xrightarrow{α_{k,i+1}} … \xrightarrow{α_{k,n_k}} q_{k,n_k}$ $p_k^{(i)} : q_{k,i} \xrightarrow{α_{k,i+1}} q_{k,i+1} \xrightarrow{α_{k,i+2}} … \xrightarrow{α_{k,n_k-i}} q_{k,n_k-i}$ $0 \le i \le \frac{n_k}2$ $Δ$

$(q_S, ε, q_{k,i})$ untuk semua seperti di atas $i$
$(q_{k, n_k-i}, ε, q_F)$ untuk semua seperti di atas $i$

$L(N)$ teratur dengan konstruksi.

Bukti sketsa bahwa : Misalkan . Dengan konstruksi kita tahu bahwa harus cocok setidaknya pada satu jalur di atas. Setiap lintasan ini milik lintasan di , yang berisi awalan tambahan dan akhiran panjang . Pilih sebagai kata yang dijelaskan oleh awalan ini dan yang dijelaskan dengan akhiran. Kami menemukan bahwa , dengan . Dengan alasan yang sama kita menemukan untuk setiap jalan di . Biarkan menjadi panjang dan $L(N) = L_2$ $w ∈ L(N)$ $w$ $p_k^{(i)}$ $D$ $i$ $x$ $y$ $xwy ∈ L$ $|x| = |y| = i$ $w ∈ L_2$ $N$ $i$ $x$ $y$ milik . untuk beberapa bentuk . $w$ $p_k^{(i)}$ $k$ $w$

Dengan demikian . $L(N) = L_2$

ipsec
sumber

Karena ada banyak jalan yang tak terhingga, pernyataan "Ini bisa dilakukan secara efektif" tampaknya perlu penjelasan. Perhatikan bahwa tidak sepenuhnya diperlukan untuk menggunakan properti itu, lihat jawaban oleh Yuval, yang (bagi saya) adalah versi "tidak efektif" dari argumen yang sama.

Hendrik

Kamu benar. Anda tidak perlu mempertimbangkan loop dua kali. Titik kritis berikutnya tampaknya ada beberapa milik , karena dengan menggabungkan jalur ada bisa muncul jalur baru. Anda lihat saya belum memeriksa bukti saya secara menyeluruh, tetapi saya percaya semua masalah ini dapat diselesaikan.

p_{k}^{(i)}

$p_k^{(i)}$

w

$w$

ipsec

Keteraturan tengah kata yang tepat dari bahasa biasa

Jawaban: