Bagaimana cara membuktikan suatu bahasa secara teratur?

48

Ada banyak metode untuk membuktikan bahwa suatu bahasa tidak teratur , tetapi apa yang harus saya lakukan untuk membuktikan bahwa beberapa bahasa itu teratur?

Misalnya, jika saya diberi tahu bahwa adalah biasa, bagaimana saya bisa membuktikan bahwa berikut ini juga teratur?L LL

L:={wL:uv=w for uΣL and vΣ+}

Bisakah saya menggambar robot hingga nondeterministis untuk membuktikan ini?

corium
sumber
1
ada kesalahan ketik dalam definisi , harap edit untuk memperbaikinya. L
Ran G.
2
"Menggambar" bukanlah bukti; Anda harus memberikan NFA dan membuktikannya menerima bahasa.
Raphael
Saya pikir definisi bahasa masih tidak masuk akal ...
hugomg
2
Bagaimanapun, bahasa spesifiknya tidak relevan jika pertanyaannya adalah "bisakah saya menggambar NFA untuk membuktikannya teratur". @corium, bisakah kita mengedit pertanyaan untuk mencerminkan pertanyaan yang lebih umum: "bagaimana membuktikan bahwa tertentu biasa"? L
Ran G.

Jawaban:

48

Ya, jika Anda dapat menemukan salah satu dari yang berikut:

untuk beberapa bahasa , maka L adalah reguler. Ada model yang lebih setara , tetapi di atas adalah yang paling umum.LL

Ada juga properti yang berguna di luar dunia "komputasi". juga biasa jikaL

  • itu terbatas,
  • Anda dapat membangunnya dengan melakukan operasi tertentu pada bahasa reguler, dan operasi itu ditutup untuk bahasa biasa , seperti

    • persimpangan,
    • melengkapi,
    • homomorfisme,
    • pembalikan,
    • hasil bagi-kiri atau kanan,
    • transduksi reguler

    dan lebih banyak lagi , atau

  • menggunakan teorema Myhill – Nerode jika jumlah kelas ekivalensi untuk adalah terbatas.L

Dalam contoh yang diberikan, kami memiliki beberapa (biasa) Bahasamu sebagai dasar dan ingin mengatakan sesuatu tentang bahasa L ' berasal dari itu. Mengikuti pendekatan pertama - membuat model yang cocok untuk L - kita dapat mengasumsikan model mana pun yang setara untuk L yang kita inginkan; itu akan tetap abstrak, tentu saja, karena L tidak diketahui. Dalam pendekatan kedua, kita dapat menggunakan L secara langsung dan menerapkan properti closure untuk mencapai deskripsi L .LLLLLLL

Ran G.
sumber
4
Mungkin juga perlu dicatat bahwa membuktikan bahasa itu terbatas sudah cukup untuk menunjukkan bahwa bahasa itu teratur. Itu bisa bermanfaat, terutama dalam bukti non-konstruktif oleh kasus.
Patrick87
2
regexp seperti yang ditemukan dalam bahasa pemrograman dapat melakukan lebih dari bahasa biasa. Anda harus membatasi untuk konstruksi "klasik".
David Lewis
4
@ DavidLewis: Di situs ini, Anda dapat mengasumsikan bahwa dengan "ekspresi reguler", pengertian klasik dimaksudkan.
Raphael
@ DavidLewis Saya setuju, orang harus menghindari "regexp" dalam konteks teori untuk menghindari kebingungan.
Raphael
Perhatikan bahwa untuk salah satu dari empat peluru pertama, Anda akan memerlukan bukti yang menunjukkan bahwa representasi Anda memang benar.
Raphael
10

Metode dasar

  1. Automata terbatas (mungkin tidak deterministik, dengan transisi kosong).
  2. Ekspresi reguler.
  3. Persamaan linear Kanan (atau Kiri, tetapi tidak keduanya), seperti mana K dan L adalah reguler.X=KX+LKL
  4. Tata bahasa reguler (Tipe 3).
  5. Operasi mempertahankan bahasa reguler (operasi Boolean, produk, bintang, shuffle, morfisme, inversi morfisme, pembalikan, dll.)
  6. Diakui oleh monoid terbatas.

Metode logis (sering digunakan dalam verifikasi formal)

  1. Logika urutan kedua monadik (teorema Büchi).
  2. Logika temporal linier (teorema Kamp).
  3. Teorema pohon Rabin (Logika urutan kedua Monadik dengan dua penerus). Sangat kuat.

Metode lanjutan

  1. Lemma pemompaan yang canggih. Lihat misalnya
    [1] J. Jaffe, A lemma pemompaan yang diperlukan dan cukup untuk bahasa reguler, Sigact News - SIGACT 10 (1978) 48-49.
    [2] A. Ehrenfeucht, R. Parikh, dan G. Rozenberg, Memompa lemma untuk set reguler, SIAM J. Comput. 10 (1981), 536-541.
    [3] S. Varricchio, Kondisi pemompaan untuk set reguler, SIAM J. Comput. 26 (1997) 764-771.

  2. Perintah baik kuasi. Lihat
    [4] W. Bucher, A. Ehrenfeucht, D. Haussler, Total regulator yang dihasilkan oleh relasi derivasi, Theor. Komputasi. Sci. 40 (1985) 131–148.
    [5] M. Kunz, Solusi Reguler untuk Ketidaksetaraan Bahasa dan Perintah yang Baik .

  3. Dukungan seri rasional.N

  4. Metode aljabar berdasarkan Transduksi (lihat juga Operasi yang mempertahankan bahasa reguler ).

J.-E. Pin
sumber
4

Jawaban oleh Ran G. memberikan daftar yang cukup luas dari model-model yang setara yang dapat digunakan untuk menentukan bahasa reguler (dan daftar berjalan, automata dua arah, logika MSO, tapi itu tercakup oleh tautan di bawah 'model yang lebih setara) '). Dan seperti yang ditekankan Raphael, kita perlu argumen untuk meyakinkan hadirin bahwa representasi yang dipilih memang benar.

Mempertimbangkan kembali pertanyaan, ia menambahkan 'Misalnya '. Itu berarti kita harus memberikan konstruksi yang valid bahwa, mengingat salah satu model di atas kita asumsikan menentukan bahasa L , mengubah model itu menjadi satu untuk L . Ini umumnya akan menjadi jenis model yang sama, tetapi tidak harus: kita misalnya dapat mulai dengan FSA deterministik untuk L dan diakhiri dengan model nondeterminitic untuk L .LLLL

Ini termasuk kemungkinan untuk menggunakan operasi penutupan: dalam operasi yang diberikan secara eksplisit dalam contoh kita memiliki .L=(ΣL)Σ

Jadi, poin saya adalah bahwa jawabannya adalah besar, tetapi kita harus menambahkan "dari ke L ' pembangunan", bila tidak membangun bahasa tertentu dari awal.LL

Hendrik Jan
sumber
1
Saya tidak yakin apa yang Anda maksud. Jika saya memiliki beberapa model untuk , saya dapat mengubahnya menjadi salah satu yang setara lainnya. L
Raphael
@ Raphael Maaf saya benar. Jawaban sebelumnya sepertinya menjelaskan bahwa kita dapat membuat deskripsi bahasa (seperti otomat, operasi, dll.). Saya setuju. Namun, pertanyaannya tampaknya tentang sifat penutupan, lihat contoh yang diberikan. Poin itu saya tidak ada dalam jawaban lain: untuk membuktikan properti penutupan Anda menganggap Anda memiliki deskripsi, dan membangun yang baru.
Hendrik Jan
1
Ah, ini ! Sekarang saya mengerti, salah saya. Saya setuju, aspek ini hilang dari jawaban Ran. L
Raphael
1
Saya tidak yakin mengapa itu hilang (atau apa yang sebenarnya hilang). Katakanlah Anda memiliki biasa , dan Anda ingin membuktikan L adalah biasa juga, Anda bisa mulai dengan L ' 's DFA dan menggunakannya untuk membangun sebuah DFA untuk L . Tapi ini dicakup oleh "membangun DFA untuk L " .. tidak ada batasan untuk menggunakan L otomat untuk tugas itu (dan tentu saja, jika L didefinisikan melalui L Anda akan dipaksa untuk menggunakan otomat L ..) . Hal yang sama berlaku untuk regexp, penutupan, tata bahasa, dll.LLLLLLLLL
Ran G.
1
Oh oke. Sebenarnya, saya lebih suka mengedit pertanyaan, dan menghapus bagian "misalnya", sehingga menjadikan pertanyaan lebih umum, dan referensi untuk pertanyaan serupa di masa mendatang .. (:
Ran G.
4

Kadang-kadang Anda akan menemukan bahasa yang ditetapkan sebagai "semua string di mana setiap k substring -element dari s memenuhi ", di mana k adalah beberapa konstanta tetap. Dalam hal ini, bahasanya akan teratur. Idenya di sini adalah untuk mendefinisikan otomat terbatas yang beberapa di antaranya menyatakan "mengingat" simbol input k yang paling baru dilihat , seperti dalam jawaban untuk pertanyaan ini .sks<some property>kk

Rick Decker
sumber
4

Metode lain, tidak tercakup oleh jawaban di atas, adalah transformasi otomat terbatas . Sebagai contoh sederhana, mari kita tunjukkan bahwa bahasa reguler ditutup di bawah operasi acak , didefinisikan sebagai berikut:

L1SL2={x1y1xnynΣ:x1xnL1,y1ynL2}
Anda dapat menunjukkan penutupan di bawah acak menggunakan properti penutupan, tetapi Anda juga dapat menunjukkannya secara langsung menggunakan DFA. Misalkan adalah DFA yang menerima L i (untuk i = 1 , 2 ). Kami membangun baru DFA Σ , Q , F , δ , q 0 sebagai berikut:Ai=Σ,Qi,Fi,δi,q0iLii=1,2Σ,Q,F,δ,q0
  • Himpunan status adalah , di mana komponen ketiga mengingat apakah simbol berikutnya adalah x i (ketika 1) atau y i (ketika 2).Q1×Q2×{1,2}xiyi
  • Keadaan awal adalah .q0=q01,q02,1
  • Status penerima adalah .F=F1×F2×{1}
  • Fungsi transisi didefinisikan oleh dan δ ( q 1 , q 2 , 2 , σ ) = q 1 , δ 2 ( q 2 , σδ(q1,q2,1,σ)=δ1(q1,σ),q2,2 .δ(q1,q2,2,σ)=q1,δ2(q2,σ),1

Versi yang lebih canggih dari metode ini melibatkan menebak . Sebagai contoh, mari kita tunjukkan bahwa bahasa reguler ditutup dengan pembalikan , yaitu, (Di sini ( w 1 ... w n ) R = w n ... w 1

LR={wR:wΣ}.
(w1wn)R=wnw1.) Ini adalah salah satu operasi penutupan standar, dan penutupan dengan pembalikan dengan mudah mengikuti manipulasi ekspresi reguler (yang dapat dianggap sebagai mitra transformasi otomat terbatas hingga ekspresi reguler) - hanya membalikkan ekspresi reguler. Tapi Anda juga bisa membuktikan penutupan menggunakan NFA. Misalkan bahwa diterima oleh DFA Σ , Q , F , δ , q 0 . Kami membangun sebuah NFA Σ , Q ' , F ' , δ ' , q ' 0 , di manaLΣ,Q,F,δ,q0Σ,Q,F,δ,q0
  • Himpunan negara adalah .Q=Q{q0}
  • Keadaan awal adalah .q0
  • Keadaan penerima unik adalah .q0
  • Fungsi transisi didefinisikan sebagai berikut: , dan untuk keadaan apa pun q Q dan σ Σ , δ ( q , σ ) = { q : δ ( q , σ ) = q } .δ(q0,ϵ)=FqQσΣδ(q,σ)={q:δ(q,σ)=q}

(Kita dapat menghilangkan jika kita mengizinkan beberapa status awal.) Komponen menebak di sini adalah status akhir kata setelah pembalikan.q0


Menebak seringkali melibatkan juga verifikasi. Salah satu contoh sederhana adalah penutupan di bawah rotasi : Misalkan L diterima oleh DFA Σ , Q , F , δ , q 0 . Kami membangun sebuah NFA Σ , Q ' , F ' , δ ' , q '

R(L)={yxΣ:xyL}.
LΣ,Q,F,δ,q0, yang beroperasi sebagai berikut. NFA menebak pertama kaliq=δ(q0,x). Kemudian memverifikasi bahwaδ(q,y)Fdan bahwaδ(q0,x)=q, bergerak dariykex secaranon-deterministik. Ini dapat diformalkan sebagai berikut:Σ,Q,F,δ,q0q=δ(q0,x)δ(q,y)Fδ(q0,x)=qyx
  • Statusnya adalah . Terlepas dari keadaan awal q ' 0 , negara-negara yang q , q c u r r , s , di mana q adalah negara yang kami menduga, q c u r r adalah kondisi saat ini, dan s menspesifikasikan apakah kita berada di si yQ={q0}Q×Q×{1,2}q0q,qcurr,sqqcurrsybagian dari input (ketika 1) atau pada bagian dari input (ketika 2).x
  • Negara-negara akhir adalah : kita menerima ketika δ ( q 0 , x ) = q .F={q,q,2:qQ}δ(q0,x)=q
  • Transisi menerapkan menebak q .δ(q0,ϵ)={q,q,1:qQ}q
  • Transisi (untuk setiap q , q c u r rQ dan s { 1 , 2 } ) mensimulasikan DFA asli.δ(q,qcurr,s,σ)=q,δ(qcurr,σ),sq,qcurrQs{1,2}
  • Transisi , untuk setiap q Q dan q fF , menerapkan bergerak dari y bagian ke x bagian. Ini hanya diizinkan jika kita telah mencapai keadaan akhir pada bagian y .δ(q,qf,1,ϵ)=q,q0,2qQqfFyxy

Varian lain dari teknik ini menggunakan penghitung terbatas. Sebagai contoh, mari kita pertimbangkan untuk mengubah penutupan jarak sunting : Mengingat DFA Σ , Q , F , δ , q 0 untuk L , e membangun sebuah NFA Σ , Q '

Ek(L)={xΣ: there exists yL whose edit distance from x is at most k}.
Σ,Q,F,δ,q0L untuk E k ( L ) sebagai berikut:Σ,Q,F,δ,q0Ek(L)
  • Himpunan status adalah , di mana item kedua menghitung jumlah perubahan yang dilakukan sejauh ini.Q=Q×{0,,k}
  • Keadaan awal adalah .q0=q0,0
  • Status penerima adalah .F=F×{0,,k}
  • q,σ,iδ(q,σ),iδ(q,i,σ)
  • q,i+1δ(q,i,σ)q,σ,ii<k
  • δ(q,σ),i+1δ(q,i,ϵ)q,σ,ii<k
  • δ(q,σ),i+1δ(q,i,τ)q,σ,τ,ii<k
Yuval Filmus
sumber
3

Suatu bahasa adalah normal jika Anda dapat menulis pemindai yang memutuskan string acak apakah mereka termasuk dalam bahasa yang menggunakan tidak lebih dari jumlah memori yang tetap - yaitu pengenalan dapat dilakukan dalam ruang O (1) .

reinierpost
sumber
O (1) ruang, maksud Anda? Bagaimanapun, ini dicakup oleh fakta bahwa DFA sudah cukup; mungkin bermanfaat untuk secara eksplisit mencatat kesetaraan ini dalam hal pemrograman.
Raphael
Ya, itu hanya perspektif yang berbeda.
reinierpost
3

Transformasi ekspresi reguler adalah salah satu cara untuk membuktikan penutupan di bawah operasi tertentu. Dua contoh paling sederhana adalah penutupan di bawah pembalikan dan penutupan di bawah homomorfisme .

rLLRL

  • ϵR=ϵσR=σR=
  • (r1+r2)R=(r1R+r2R)(r)R=(rR)(r1r2)R=r2Rr1R

(r1r2)R=r2Rr1R(01)R=10rRLR

h:ΣΔrLh(L)σrh(σ)

Yuval Filmus
sumber
0

Cara lain adalah membangun bahasa menggunakan operasi di mana Anda tahu mereka ditutup. Ini merupakan perluasan untuk menunjukkan ekspresi reguler, karena Anda memiliki lebih banyak operasi yang tersedia (membalikkan string, komplemen, persimpangan, memotong sepotong, tetap bagian, homomorfisma dan homomorfisma terbalik, ...)

vonbrand
sumber
2
Itu sudah disebutkan dalam jawaban Ran.
Raphael