Bagaimana cara membuktikan suatu bahasa secara teratur?

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 $L$$L'$

$\qquad \displaystyle L' := \{w \in L: uv = w \text{ for } u \in \Sigma^* \setminus L \text{ and } v \in \Sigma^+ \}$

Bisakah saya menggambar robot hingga nondeterministis untuk membuktikan ini?

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

• deterministic finite automaton (DFA),
• otomat hingga nondeterministik (NFA),
• ekspresi reguler (regexp dari bahasa formal) atau
• tata bahasa biasa

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

Ada juga properti yang berguna di luar dunia "komputasi". juga biasa jika$L$

• 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 ′ .$L$$L'$$L'$$L$$L$$L$$L'$

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 + L$$K$$L$
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.$\mathbb{N}$

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

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 ′ .$\dots$$L$$L'$$L$$L'$

Ini termasuk kemungkinan untuk menggunakan operasi penutupan: dalam operasi yang diberikan secara eksplisit dalam contoh kita memiliki .$L'= (\Sigma^* \setminus L) \cdot \Sigma^*$

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

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 .$s$$k$$s$<some property>$k$$k$

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:

$$L_1 \mathop{S} L_2 = \{ x_1y_1 \ldots x_n y_n \in \Sigma^* : x_1 \ldots x_n \in L_1, y_1 \ldots y_n \in L_2 \}$$ 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:$A_i = \langle \Sigma, Q_i, F_i, \delta_i, q_{0i} \rangle$$L_i$$i=1,2$$\langle \Sigma, Q, F, \delta, q_0 \rangle$

• Himpunan status adalah , di mana komponen ketiga mengingat apakah simbol berikutnya adalah x i (ketika 1) atau y i (ketika 2).$Q_1 \times Q_2 \times \{1,2\}$$x_i$$y_i$
• Keadaan awal adalah .$q_0 = \langle q_{01}, q_{02}, 1 \rangle$
• Status penerima adalah .$F = F_1 \times F_2 \times \{1\}$
• Fungsi transisi didefinisikan oleh dan δ ( ⟨ q 1 , q 2 , 2 ⟩ , σ ) = ⟨ q 1 , δ 2 ( q 2 , $\delta(\langle q_1, q_2, 1 \rangle, \sigma) = \langle \delta_1(q_1,\sigma), q_2, 2 \rangle$ .$\delta(\langle q_1, q_2, 2 \rangle, \sigma) = \langle q_1, \delta_2(q_2,\sigma), 1 \rangle$

---

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

$$L^R = \{ w^R : w \in \Sigma^* \}.$$ $(w_1\ldots w_n)^R = w_n \ldots w_1$.) 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 mana$L$$\langle \Sigma, Q, F, \delta, q_0 \rangle$$\langle \Sigma, Q', F', \delta', q'_0 \rangle$

• Himpunan negara adalah .$Q' = Q \cup \{q'_0\}$
• Keadaan awal adalah .$q'_0$
• Keadaan penerima unik adalah .$q_0$
• Fungsi transisi didefinisikan sebagai berikut: , dan untuk keadaan apa pun q ∈ Q dan σ ∈ Σ , δ ( q ′ , σ ) = { q : δ ( q , σ ) = q ′ } .$\delta'(q'_0,\epsilon) = F$$q \in Q$$\sigma \in \Sigma$$\delta(q', \sigma) = \{ q : \delta(q,\sigma) = q' \}$

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

---

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 \in \Sigma^* : xy \in L \}.$$ $L$$\langle \Sigma, Q, F, \delta, q_0 \rangle$, 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:$\langle \Sigma, Q', F', \delta', q'_0 \rangle$$q=\delta(q_0,x)$$\delta(q,y) \in F$$\delta(q_0,x) = q$$y$$x$

• 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 $Q' = \{q'_0\} \cup Q \times Q \times \{1,2\}$$q'_0$$\langle q,q_{curr}, s \rangle$$q$$q_{curr}$$s$$y$bagian dari input (ketika 1) atau pada bagian dari input (ketika 2).$x$
• Negara-negara akhir adalah : kita menerima ketika δ ( q 0 , x ) = q .$F' = \{\langle q,q,2 \rangle : q \in Q\}$$\delta(q_0,x)=q$
• Transisi menerapkan menebak q .$\delta'(q'_0,\epsilon) = \{\langle q,q,1 \rangle : q \in Q\}$$q$
• Transisi (untuk setiap q , q c u r r ∈ Q dan s ∈ { 1 , 2 } ) mensimulasikan DFA asli.$\delta'(\langle q,q_{curr},s \rangle, \sigma) = \langle q,\delta(q_{curr},\sigma),s \rangle$$q,q_{curr} \in Q$$s \in \{1,2\}$
• Transisi , untuk setiap q ∈ Q dan q f ∈ F , menerapkan bergerak dari y bagian ke x bagian. Ini hanya diizinkan jika kita telah mencapai keadaan akhir pada bagian y .$\delta'(\langle q,q_f,1 \rangle, \epsilon) = \langle q,q_0,2 \rangle$$q \in Q$$q_f \in F$$y$$x$$y$

---

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

$$E_k(L) = \{ x \in \Sigma^* : \text{ there exists $y \in L$ whose edit distance from $x$ is at most $k$} \}.$$ $\langle \Sigma, Q, F, \delta, q_0 \rangle$$L$ untuk E k ( L ) sebagai berikut:$\langle \Sigma, Q', F', \delta', q'_0 \rangle$$E_k(L)$

• Himpunan status adalah , di mana item kedua menghitung jumlah perubahan yang dilakukan sejauh ini.$Q' = Q \times \{0,\ldots,k\}$
• Keadaan awal adalah .$q'_0 = \langle q_0,0 \rangle$
• Status penerima adalah .$F' = F \times \{0,\ldots,k\}$
• $q,\sigma,i$$\langle \delta(q,\sigma), i \rangle \in \delta'(\langle q,i \rangle, \sigma)$
• $\langle q,i+1 \rangle \in \delta'(\langle q,i \rangle, \sigma)$$q,\sigma,i$$i < k$
• $\langle \delta(q,\sigma), i+1 \rangle \in \delta'(\langle q,i \rangle, \epsilon)$$q,\sigma,i$$i < k$
• $\langle \delta(q,\sigma), i+1 \rangle \in \delta'(\langle q,i \rangle, \tau)$$q,\sigma,\tau,i$$i < k$

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

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 .

$r$$L$$L^R$$L$

• $\epsilon^R = \epsilon$$\sigma^R = \sigma$$\emptyset^R = \emptyset$
• $(r_1+r_2)^R = (r_1^R + r_2^R)$$(r^*)^R = (r^R)^*$$(r_1r_2)^R = r_2^R r_1^R$

$(r_1r_2)^R = r_2^R r_1^R$$(0^*1^*)^R = 1^*0^*$$r^R$$L^R$

$h\colon \Sigma \to \Delta^*$$r$$L$$h(L)$$\sigma$$r$$h(\sigma)$

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, ...)