Automaton terhingga

Automaton terhingga (bahasa Inggeris: finite state machine atau finite automaton) ialah model pengiraan bagi sebuah komputer primitif. Automaton ini terdiri daripada beberapa keadaan dan beberapa peralihan, dan boleh menerima atau menolak rentetan yang diberikan kepadanya.

Contoh

Secara tidak formal, kita memerihalkan automaton terhingga dengan gambar rajah peralihan yang menggambarkannya:

Automaton dibina daripada keadaan; dalam rajah ini terdapat tiga keadaan berbentuk bulatan, iaitu q₀, q₁ dan q₂. Di antara keadaan ini terdapat peralihan, iaitu anak panah. Automaton juga mesti mempunyai keadaan awal, iaitu keadaan q₀. Keadaan awal biasanya ditunjukkan dengan anak panah yang menuju kepadanya tetapi tidak keluar dari mana-mana keadaan. Selain itu, automaton biasanya mempunyai keadaan akhir yang dilukis dengan garisan berganda; dalam rajah ini keadaan akhir ialah q₂.

Automaton yang dibina sebegini menerima rentetan tertentu. Kita memasukkan rentetan ke dalam automaton dan automaton itu cuba menerimanya. Jika rentetan itu diterima, automaton menjawab YA; jika tidak, automaton menjawab TIDAK. Automaton kita cuba menerima rentetan yang terdiri daripada huruf “a, b, c”, jadi kita boleh mencuba rentetan “abbc”.

Kita bermula pada keadaan awal q₀, dan input ialah rentetan “abbc”. Seterusnya kita mengikut anak panah.

Rentetan dibaca seperti biasa dari kiri ke kanan, jadi simbol pertama yang kita ambil ialah “a”. Anak panah bagi input “a” menuju ke keadaan q₁. Kita beralih ke sana dan membuang simbol “a” daripada rentetan. Kini input ialah rentetan “bbc”:

Anak panah bagi input “b” menuju kembali ke nod q₁. Sekali lagi kita membuang huruf pertama, dan input menjadi rentetan “bc”. Kita kekal pada keadaan q₁ sekali lagi. Akhirnya input ialah rentetan “c”. Dari keadaan q₁, anak panah bagi input “c” membawa kita ke keadaan q₂.

Semua huruf dalam rentetan input telah habis dibaca dan kita berada pada keadaan q₂, iaitu keadaan akhir. Oleh itu, automaton terhingga ini menerima rentetan “abbc”.

Jika pada penghujungnya kita tidak berada pada keadaan penerimaan, automaton tidak akan menerima rentetan itu. Automaton juga tidak menerima rentetan jika pada suatu keadaan tiada anak panah yang boleh diikuti. Contohnya, bagi input “ab” kita sampai ke keadaan q₁ dan berhenti di situ — automaton tidak menerima rentetan sebegini. Jika kita menguji rentetan “aabbc”, kita juga tidak bernasib baik kerana tiada anak panah bagi huruf “a” yang keluar dari keadaan q₁.

Jadi, automaton terhingga digunakan untuk mengenal pasti suatu set rentetan. Dalam amalan, automaton boleh digunakan, misalnya, untuk menentukan sama ada rentetan input ialah alamat e-mel yang sah.

Takrif automaton terhingga

Gambaran intuitif tentang automaton terhingga tadi perlu diformalkan supaya kita boleh bekerja dengan automaton dengan lebih baik.

Kita katakan bahawa automaton terhingga (berketentuan) ialah 5-tupel ⟨Q, Σ, δ, q₀, F⟩, dengan

• Q ialah set terhingga keadaan,
• Σ (sigma besar) ialah abjad (set terhingga simbol atau huruf),
• δ: Q × Σ ⟶ Q ialah fungsi peralihan,
• q₀ ∈ Q ialah keadaan awal,
• F ⊆ Q ialah set keadaan akhir (keadaan penerimaan).

Jika kita kembali kepada automaton tadi,

kita boleh mengatakan bahawa set keadaan Q mengandungi tiga keadaan, Q = {q₀, q₁, q₂}. Abjad Σ mengandungi huruf yang membentuk rentetan yang akan diterima atau ditolak oleh automaton. Di sini abjadnya mungkin Σ= {a, b, c}, tetapi boleh juga sebarang superset baginya. Keadaan awal q₀ ialah keadaan q₀; tiada perubahan di situ. Set keadaan akhir dalam automaton ini mengandungi satu keadaan sahaja, F = {q₂}.

Fungsi peralihan pula ialah tiga anak panah berlabel huruf itu. Jika tatatanda δ: Q × Σ ⟶ Q mengelirukan anda, maksudnya cuma δ ialah suatu fungsi (atau lebih tepat, pemetaan) yang menerima dua parameter: satu keadaan daripada Q dan satu huruf daripada Σ. Apabila dipanggil, fungsi itu memulangkan keadaan baharu. Fungsi peralihan kita boleh ditakrifkan dengan jadual seperti berikut:

$$\begin{array}{ccc}Q& \mathrm{\Sigma }& \to Q\\ q_0& a& q_1\\ q_1& b& q_1\\ q_1& c& q_2\end{array}$$

Jika kita memanggil δ(q₁, c), baris ketiga digunakan dan fungsi itu memulangkan keadaan q₂ — sama seperti dalam gambar rajah. Jika kita berada pada keadaan q₁ dan input ialah huruf “c”, kita sampai ke keadaan q₂. Sebelum kita mentakrifkan secara formal maksud automaton menerima suatu rentetan, kita gunakan dahulu kefahaman intuitif tentang konsep ini dan melihat beberapa contoh lain.

Contoh lain

1. Bina automaton atas abjad binari, iaitu Σ= {0, 1}, yang hanya menerima rentetan yang berakhir dengan digit satu. Contohnya, automaton itu menerima rentetan 1, 01, 000001, 0101011.

   

   Automaton kita mempunyai dua keadaan — keadaan awal q₀ dan keadaan akhir q₁. Setiap kali input ialah digit 1, kita beralih ke keadaan akhir q₁ dan kekal di situ. Sebaliknya, jika input ialah digit 0, kita beralih ke keadaan bukan akhir q₀ dan kekal di situ juga.

2. Bina automaton atas abjad binari yang hanya menerima rentetan yang huruf pertamanya berbeza daripada huruf terakhirnya.

   

   Pada langkah pertama lagi, automaton ini terbahagi kepada dua “subautomaton”. Jika rentetan bermula dengan sifar, automaton memasuki bahagian kiri dan kekal di situ; jika rentetan bermula dengan satu, automaton beralih ke bahagian kanan. Selepas itu prosesnya biasa sahaja: jika kita berada di bahagian kiri dan input ialah 1, kita beralih ke keadaan akhir dan kekal di situ. Jika input ialah 0, kita beralih ke keadaan q₁, yang bukan keadaan akhir.

   Berbeza daripada automaton sebelum ini, automaton ini mempunyai lebih daripada satu keadaan akhir, iaitu F = {q₃, q₄}.

3. Bina automaton atas abjad binari yang hanya menerima rentetan yang tidak mengandungi dua sifar berturut-turut.

   

   Automaton ini menarik atas dua sebab. Pertama, automaton ini menerima rentetan kosong. Kita boleh cuba memasukkan rentetan kosong ke dalam automaton, dan automaton akan menerimanya jika keadaan awal juga merupakan keadaan akhir, seperti dalam automaton ini. Oleh sebab rentetan kosong tidak mengandungi dua sifar berturut-turut, hasil ini betul. Kedua, semua keadaan dalam automaton ini ialah keadaan akhir. Satu-satunya kes apabila automaton tidak menerima rentetan ialah apabila tiada peralihan yang keluar dari suatu keadaan. Hal ini berlaku pada keadaan q₁, yang tiada peralihan bagi 0, kerana jika ada, rentetan itu akan mengandungi dua sifar berturut-turut.

4. Bina automaton atas abjad {-,+,.,0,1,…,9} yang hanya menerima rentetan yang mewakili nombor. Maksudnya, sama ada integer seperti 2, 548, 98263, atau nombor perpuluhan seperti 5584.48, 3.14, kedua-duanya juga dalam versi negatif dengan tanda tolak -2, -548, -3.14 dan dengan tanda tambah yang ditulis secara eksplisit, iaitu +2, +548, +3.14. Selain itu, kita mesti dapat menulis nombor 0.123 sebagai .123 sahaja (tanpa sifar di hadapan), termasuk dengan kedua-dua tanda. Kita memperkenalkan tatatanda bantuan: daripada menulis sepuluh peralihan bagi sepuluh digit, kita menggunakan simbol N.

   

5. Bina automaton atas abjad binari yang hanya menerima rentetan berbentuk 0ⁿ1ⁿ, iaitu rentetan yang bermula dengan sejumlah sifar dan diikuti oleh digit satu yang sama banyak. Contoh rentetan sebegini ialah 0011, 00001111, 01.

   Automaton sebegini tidak dapat dibina kerana kita tidak dapat “mengingati” bilangan sifar di mana-mana. Kita perlu membina beberapa “subautomaton”, seperti dalam contoh kedua, tetapi bilangan “subautomaton” itu mestilah tak terhingga, satu bagi setiap nilai n.

Formalisasi pengiraan automaton

Kita telah mentakrifkan automaton terhingga secara formal. Seterusnya kita perlu mentakrifkan apa yang sebenarnya dilakukan oleh automaton itu, iaitu kita mentakrifkan pengiraan automaton.

Konfigurasi automaton: Kita katakan bahawa pasangan ⟨q, w⟩ ∈ Q × Σ^∗ ialah konfigurasi automaton, dengan q ialah keadaan semasa automaton dan w ialah bahagian rentetan yang belum dibaca. Σ^∗ ialah tutupan abjad Σ, iaitu set semua rentetan yang boleh dibentuk daripada huruf abjad Σ. Tutupan ini juga mengandungi rentetan kosong, yang ditandakan dengan ε.

Jika kita mempunyai automaton ⟨Q, Σ, δ, q₀, F⟩ dan cuba menerima rentetan w, automaton itu berada dalam konfigurasi awal ⟨q₀, w⟩. Jika kita kembali kepada automaton

dan mahu menerima rentetan w = abbc, konfigurasi awalnya ialah ⟨q₀, abbc⟩.

Langkah pengiraan ditakrifkan sebagai hubungan ↦ antara set (Q × Σ^∗) × (Q × Σ^∗), iaitu antara konfigurasi automaton. Katakan w = w₀w₁… w_n mewakili bahagian rentetan w yang belum dibaca. Kita katakan bahawa pasangan ⟨q₁, w₀w₁… w_n⟩ dan ⟨q₂, w₁… w_n⟩ berada dalam hubungan ↦, ditulis sebagai

$$⟨q_1,w_0{w}_1\dots w_n⟩\mapsto ⟨q_2,w_1\dots w_n⟩,$$

jika dan hanya jika δ(q₁, w₀) = q₂. Kembali kepada contoh kita, konfigurasi awal ialah ⟨q₀, abbc⟩. Daripada gambar rajah, kita lihat bahawa bagi input “a” kita boleh beralih ke keadaan q₁. Oleh itu, kita boleh menulis

$$⟨q_0,abbc⟩\mapsto ⟨q_1,bbc⟩,$$

kerana δ(q₀, a) = q₁. Dengan ini kita telah melakukan satu langkah pengiraan — kita melihat keadaan yang patut dituju bagi input tertentu (= huruf pertama bahagian rentetan yang belum dibaca), beralih ke sana dan membuang huruf pertama daripada bahagian rentetan yang belum dibaca. Hasilnya ialah konfigurasi baharu.

Tutupan refleksif dan transitif bagi hubungan langkah pengiraan ditandakan dengan ↦ ^∗. Jika kita menulis K₁ ↦ ^∗ K₂, dengan K₁, K₂ ialah konfigurasi automaton, maksudnya dari konfigurasi K₁ kita boleh sampai ke konfigurasi K₂ melalui beberapa langkah pengiraan. Dengan kata lain, wujud jujukan terhingga konfigurasi seperti berikut:

$$K_1\mapsto K_{11}\mapsto K_{12}\mapsto K_{13}\mapsto \cdots \mapsto K_2$$

Contohnya, dalam automaton kita, ⟨q₀, abbc⟩ ↦ ^∗ ⟨q₁,bc⟩, kerana selepas dua langkah pengiraan, rentetan yang tinggal ialah “bc” dan kita kekal pada keadaan q₁. Maksudnya, wujud jujukan konfigurasi berikut:

$$⟨q_0,abbc⟩\mapsto ⟨q_1,bbc⟩\mapsto ⟨q_1,bc⟩$$

Automaton menerima rentetan w jika dan hanya jika wujud q_f ∈ F yang memenuhi $$⟨q_0,w⟩{\mapsto }^{\ast }⟨q_f,\epsilon ⟩$$ Maksudnya, automaton menerima rentetan w jika dan hanya jika wujud jujukan langkah pengiraan yang berakhir dengan keseluruhan rentetan telah dibaca dan kita berada pada keadaan akhir automaton. Hakikat bahawa kita telah membaca keseluruhan rentetan dinyatakan dengan ε, iaitu rentetan kosong, di tempat rentetan dalam konfigurasi. Automaton kita menerima rentetan abbc kerana wujud jujukan konfigurasi berikut:

$$⟨q_0,abbc⟩\mapsto ⟨q_1,bbc⟩\mapsto ⟨q_1,bc⟩\mapsto ⟨q_1,c⟩\mapsto ⟨q_2,\epsilon ⟩$$

dan keadaan q₂ ialah keadaan akhir, q₂ ∈ F.

Bahasa yang diterima oleh automaton ialah set semua rentetan yang diterima oleh automaton itu. Bahasa bagi automaton A ditandakan dengan L(A). Oleh itu, L(A) ⊆ Σ^∗ dan

$$L(A)=\{w\in {\mathrm{\Sigma }}^{\ast }|A\text{ menerima rentetan }w\}$$

Bahasa nalar (regular language) ialah bahasa yang diterima oleh suatu automaton terhingga.

Dua automaton terhingga dikatakan setara jika kedua-duanya menerima bahasa yang sama. Maksudnya, automaton A₁ dan A₂ setara jika L(A₁) = L(A₂).

Sumber

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools