Automaton terhingga tak berketentuan

Automaton terhingga yang diperkenalkan dalam bab sebelum ini (singkatannya FA atau DFA) sentiasa berketentuan, iaitu pada setiap ketika jelas apa yang akan dilakukan oleh automaton itu. Sekarang kita melihat konsep yang lebih umum, iaitu automaton terhingga tak berketentuan (singkatannya NFA, daripada nondeterministic finite automaton). Dalam automaton ini boleh wujud beberapa peralihan yang keluar dari keadaan yang sama bagi simbol yang sama.

Contoh

Perhatikan gambar rajah automaton berikut:

Apakah yang luar biasa tentangnya? Dari nod q₀ keluar dua anak panah bagi simbol 0. Jika kita cuba menerima rentetan 001, nampaknya automaton tidak tahu sama ada perlu kekal pada keadaan q₀ atau mengikut peralihan ke q₁. Automaton sebegini dikatakan tak berketentuan.

Berketentuan dalam konteks ini bermakna bahawa dalam setiap situasi jelas apa yang akan dilakukan oleh automaton; tiada ruang untuk kekaburan. Automaton berketentuan mempunyai hanya satu peralihan bagi setiap keadaan dan setiap simbol. Tak berketentuan pula bermakna kekaburan — dari satu keadaan, mungkin ada, misalnya, tiga peralihan bagi simbol yang sama.

Jadi, bagaimanakah automaton membuat keputusan? Automaton tak berketentuan sentiasa memilih (kadangkala kita juga katakan “meneka”) peralihan yang membawa kepada penerimaan rentetan, jika hal itu mungkin.

Jika kita memasukkan rentetan 001 ke dalam automaton, automaton mempunyai pilihan berikut untuk memproses rentetan itu:

$\begin{array}{r} q_{0} \to q_{0} \to q_{0} \to q_{0} \\ q_{0} \to q_{0} \to q_{1} \to q_{2} \end{array}$

serta pilihan apabila automaton tidak membaca keseluruhan rentetan. Dalam pilihan pertama, automaton sentiasa kekal pada keadaan q₀; hal ini memang dibenarkan oleh peraturan peralihan. Dalam cabang kedua, automaton berani beralih ke keadaan lain dan akhirnya sampai ke keadaan q₂, iaitu keadaan akhir. Dalam cabang ini automaton akan menerima rentetan itu. Automaton tak berketentuan sentiasa memilih secara automatik cabang yang membawa kepada penerimaan rentetan, jika cabang sedemikian wujud.

Bagaimanakah automaton memilih cabang yang “menguntungkan” itu secara automatik? Kita boleh membayangkan bahawa automaton tak berketentuan meneroka semua cabang yang mungkin, dan jika menemui cabang yang menerima rentetan, automaton itu menerima rentetan tersebut. Bagaimanakah automaton boleh meneroka semua cabang? Mudah sahaja: apabila automaton berada pada keadaan yang mempunyai n anak panah bagi simbol semasa, automaton menyalin dirinya sebanyak n kali dan setiap salinan mengikut laluan yang berbeza. Dengan cara ini semua kemungkinan diteroka satu demi satu.

Perwakilan pengiraan automaton dalam bentuk pokok

Kita ubah sedikit automaton tadi:

Ketakberketentuan masih berada pada keadaan pertama. Automaton sebelum ini menerima semua rentetan yang berakhir dengan 01. Automaton yang diubah suai ini menerima semua rentetan yang mengandungi subrentetan 01. Jadi, automaton ini menerima, misalnya, rentetan 101 atau 0101. Semua cabang pengiraan mudah digambarkan dengan pokok. Contohnya, bagi rentetan 01010, pokoknya boleh kelihatan seperti berikut:

Pada mulanya kita berada pada keadaan awal q₀. Input ialah rentetan 01010, dan aksara pertama yang belum dibaca ialah 0. Dari keadaan q₀ keluar dua peralihan bagi simbol 0, iaitu ke keadaan q₀ dan q₁. Oleh itu, nod ini dalam pokok mempunyai dua anak: q₀ dan q₁. Seterusnya kita membaca simbol 1. Di sini tiada kekaburan; kita beralih ke keadaan q₀ dan q₂. Kemudian kita membaca aksara 0. Dalam cabang kiri berlaku kekaburan lagi, jadi kita membahagikan pengiraan kepada dua cabang baharu. Dalam satu cabang kita kekal pada q₀, dan dalam cabang yang lain kita beralih ke q₁. Begitulah seterusnya.

Perhatikan bahawa dua cabang berakhir pada keadaan q₂, iaitu keadaan akhir. Terdapat dua cabang pengiraan yang membolehkan automaton menerima rentetan itu. Oleh itu, automaton ini menerima rentetan 01010. Kita boleh cuba membina pokok yang serupa bagi rentetan 1000.

Pengiraan sama ada kekal pada keadaan q₀ atau beralih ke keadaan q₁, tetapi dari situ tiada lagi peralihan yang boleh diikuti kerana input yang tinggal hanya sifar, manakala keadaan q₁ hanya mempunyai peralihan bagi simbol 1. Tiada cabang pengiraan yang berakhir pada keadaan akhir, jadi automaton ini tidak menerima rentetan 1000.

Peralihan epsilon

Dalam automaton tak berketentuan, kita juga boleh menggunakan peralihan epsilon. Peralihan ini boleh dilakukan tanpa mengira simbol input, dan tanpa membaca sebarang simbol daripada rentetan. Bagaimanakah kita boleh membina automaton tak berketentuan yang menerima rentetan kosong, semua rentetan yang terdiri daripada digit satu sahaja, dan rentetan berbentuk (10)ⁿ, iaitu 10, 1010, …?

Kita membahagikan automaton kepada dua “subautomaton”. Subautomaton atas mengenal pasti rentetan yang terdiri daripada 1, manakala subautomaton bawah mengenal pasti rentetan berbentuk (10)ⁿ. Mari kita cuba menerima rentetan 111. Pada mulanya automaton berada pada keadaan q₀ dengan input rentetan 111. Oleh sebab automaton mempunyai peralihan epsilon, automaton boleh memilih untuk beralih ke keadaan q₁ atau q₂ mengikut keperluan. Kita lihat bahawa pilihan yang betul ialah beralih ke keadaan q₁, jadi automaton beralih ke sana. Pada masa itu, input masih rentetan 111! Hanya selepas itu automaton mula membaca simbol daripada rentetan dan beralih dari keadaan q₁ ke q₁ semula, sehingga keseluruhan rentetan dibaca dan diterima.

Jika kita cuba menerima 1010, automaton pada mulanya beralih ke keadaan q₂, dan hanya dari situ automaton mula memproses simbol dan sekali lagi menerima rentetan itu.

Bagi rentetan 1100, apa pun yang dilakukan oleh automaton, rentetan itu tidak dapat diterima.

Peralihan epsilon dan ketakberketentuan memudahkan banyak kerja. Contohnya, bukti bahawa kesatuan bahasa nalar ialah bahasa nalar boleh ditulis dengan jauh lebih mudah menggunakan peralihan epsilon berbanding kes automaton terhingga berketentuan. Dalam bukti itu kita mempunyai contoh automaton berikut

dan

dan kemudian kita membina automaton terhingga berketentuan yang menerima kesatuan kedua-dua bahasa itu. Dengan peralihan epsilon, automaton sebegini boleh dibina seperti berikut:

Ringkasnya, kita menambahkan keadaan awal baharu; dari keadaan ini dua peralihan epsilon menuju ke keadaan awal asal bagi automaton asal, dan itu sahaja. Automaton membuat keputusan secara tak berketentuan sama ada mencuba menerima rentetan dengan “subautomaton” pertama atau kedua.

Takrif automaton tak berketentuan

Kita telah melihat perbezaan antara automaton terhingga berketentuan dengan automaton terhingga tak berketentuan; yang tinggal hanyalah memformalkannya. Automaton terhingga berketentuan ditakrifkan sebagai 5-tupel ⟨Q, Σ, δ, q₀, F⟩, dengan Q ialah set keadaan, Σ ialah abjad, δ ialah fungsi peralihan, q₀ ialah keadaan awal dan F ialah set keadaan akhir. Satu-satunya perubahan dalam takrif automaton tak berketentuan ialah takrif fungsi peralihan.

Dalam versi berketentuan, panggilan δ(q, w) hanya boleh memulangkan satu keadaan, manakala dalam versi tak berketentuan fungsi itu boleh memulangkan beberapa keadaan — jika beberapa peralihan ditakrifkan bagi satu simbol. Oleh sebab kita juga perlu mentakrifkan peralihan epsilon, kita tandakan set Σ ∪ {ε} sebagai set Σ_ε, iaitu Σ_ε = Σ ∪ {ε}. Fungsi δ ditakrifkan sebagai

$δ : Q \times Σ_{ε} \to 2^{Q}$

Simbol 2^Q ialah set kuasa, iaitu set semua subset bagi set Q. Formalisasi pengiraan sangat serupa dengan automaton terhingga berketentuan. Konfigurasi automaton sekali lagi ialah pasangan ⟨q, w⟩ ∈ Q × Σ^∗. Langkah pengiraan ↦ ialah hubungan pada set konfigurasi yang memenuhi

$⟨ q_{i}, w_{0} w_{1} \dots w_{n} ⟩ \mapsto ⟨ q_{j}, w_{1} \dots w_{n} ⟩,$

jika dan hanya jika q_j ∈ δ(q_i, w₀). Dalam ayat inilah terletak perbezaan terbesar. Dalam automaton berketentuan, syarat ini ditulis sebagai q_j = δ(q_i, w₀) kerana fungsi δ sentiasa memulangkan satu keadaan. Versi tak berketentuan bagi fungsi peralihan memulangkan set keadaan, oleh itu digunakan simbol ∈. Tutupan refleksif dan transitif bagi hubungan ini sekali lagi ditandakan dengan ↦ ^∗. Kita katakan bahawa automaton menerima rentetan w jika dan hanya jika wujud q_f ∈ F yang memenuhi

$⟨ q_{0}, w ⟩ \mapsto^{*} ⟨ q_{f}, ε ⟩ .$

Sumber

Kandungan: Automaton terhingga, Automaton lengkap, Automaton terhingga tak berketentuan, Simulasi automaton tak berketentuan, Penukaran NFA kepada DFA

« Artikel sebelumnya: Automaton lengkap

Artikel seterusnya: Simulasi automaton tak berketentuan »