Keteraturan tengah kata yang tepat dari bahasa biasa

8

Biarkan menjadi bahasa biasa. Apakah bahasa teratur?L
L2={y:x,z  s.t.|x|=|z| and xyzL}

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 .LL2

Tomer
sumber
"tepat tengah" tampaknya menyarankan? Ngomong-ngomong, itu juga biasa! |x|=|y|=|z|
Hendrik
Sudahkah Anda mencoba barang dari pertanyaan referensi kami ?
Raphael

Jawaban:

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 Ln0AnsnsBntnts,tRs,tst

L2=n0sAntBnRs,t.
Karena hanya ada banyak kemungkinan untuk , serikat sebenarnya terbatas, dan sangat teratur.s,t
Yuval Filmus
sumber
3

Misalkan menjadi DFA untuk . Tanpa kehilangan umum, menganggap . Kami membangun ε-NFA untuk dengan cara berikut:D=(Q,Σ,δ,q0,F)LqS,qFQN=(Q{qS,qF},Σ,Δ,qS,{qF})L2

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:Dq0fFpk:q0=qk,0αk,1qk,1αk,2αk,iqk,iαk,i+1αk,nkqk,nkpk(i):qk,iαk,i+1qk,i+1αk,i+2αk,nkiqk,nki0ink2Δ

  • (qS,ε,qk,i) untuk semua seperti di atasi
  • (qk,nki,ε,qF) untuk semua seperti di atasi

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 danL(N)=L2wL(N)wpk(i)DixyxwyL|x|=|y|=iwL2Nixymilik . untuk beberapa bentuk .wpk(i)kw

Dengan demikian .L(N)=L2

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. pk(i)w
ipsec