Otomaton hingga

Otomaton hingga (bahasa Inggris: finite state machine atau finite automaton) adalah model komputasi berupa komputer sederhana yang terdiri atas beberapa state dan beberapa transisi, serta dapat menerima atau menolak string yang diberikan kepadanya.

Contoh

Secara informal, otomaton hingga dapat kita jelaskan dengan diagram transisi yang menggambarkannya:

Otomaton tersusun atas state; pada gambar ada tiga state berbentuk lingkaran, yaitu q₀, q₁, dan q₂. Di antara state-state tersebut terdapat transisi, yaitu panah-panah pada gambar. Otomaton juga harus memiliki state awal, dalam hal ini state q₀. State awal sering digambarkan dengan panah yang mengarah ke state tersebut tetapi tidak berasal dari state mana pun. Selain itu, otomaton biasanya memiliki state akhir yang digambar dengan garis ganda; pada gambar, state akhir adalah q₂.

Otomaton yang disusun seperti ini menerima string tertentu. Kita memasukkan string ke otomaton, lalu otomaton mencoba menerimanya. Jika string diterima, otomaton menjawab YA; jika tidak, otomaton menjawab TIDAK. Otomaton kita mencoba menerima string yang tersusun atas huruf “a, b, c”, sehingga kita dapat mencoba string “abbc”.

Kita mulai dari state awal q₀, dan inputnya adalah string “abbc”. Selanjutnya, kita mengikuti panah.

String dibaca seperti biasa dari kiri ke kanan, artinya simbol pertama yang kita ambil adalah “a”. Panah untuk input “a” menuju state q₁, jadi kita berpindah ke sana dan menghapus simbol “a” dari string. Sekarang inputnya adalah string “bbc”:

Panah untuk input “b” mengarah kembali ke simpul q₁. Kita kembali menghapus huruf pertama, dan inputnya menjadi string “bc”. Kita tetap berada di state q₁. Akhirnya, inputnya adalah string “c”. Dari state q₁, panah untuk input “c” membawa kita ke state q₂.

Semua huruf string input sudah habis dibaca, dan kita berada di state q₂, yang merupakan state akhir. Jadi, otomaton hingga ini menerima string “abbc”.

Jika pada akhirnya kita tidak berada di state penerima, otomaton tidak akan menerima string tersebut. Otomaton juga tidak menerima string jika di suatu state kita tidak punya tujuan untuk melanjutkan. Misalnya, untuk input “ab” kita sampai di state q₁ dan berhenti di sana — otomaton tidak menerima string seperti itu. Jika kita menguji string “aabbc”, kita juga gagal, karena dari state q₁ tidak ada panah untuk huruf “a”.

Jadi, otomaton hingga digunakan untuk mengenali suatu himpunan string. Dalam praktik, otomaton dapat digunakan, misalnya, untuk memeriksa apakah string input merupakan alamat email yang valid.

Definisi otomaton hingga

Gambaran intuitif tentang otomaton hingga di atas perlu kita formalkan agar kita dapat bekerja dengan otomaton lebih jauh dan lebih baik.

Otomaton hingga (deterministik) adalah lima-tupel ⟨Q, Σ, δ, q₀, F⟩, dengan

• Q himpunan berhingga state,
• Σ (sigma kapital) alfabet (himpunan berhingga simbol/huruf),
• δ: Q × Σ ⟶ Q fungsi transisi,
• q₀ ∈ Q state awal,
• F ⊆ Q himpunan state akhir (state penerima).

Jika kita kembali ke otomaton sebelumnya,

dapat dikatakan bahwa himpunan state Q memuat tiga state, Q = {q₀, q₁, q₂}. Alfabet Σ memuat huruf-huruf yang dapat dirangkai menjadi string, yang kemudian diterima atau ditolak oleh otomaton. Di sini alfabetnya kemungkinan besar Σ= {a, b, c}, tetapi bisa juga sembarang superhimpunannya. State awal q₀ adalah state q₀, tidak ada yang berubah. Himpunan state akhir pada otomaton ini hanya memuat satu state, F = {q₂}.

Yang dimaksud dengan fungsi transisi adalah ketiga panah berhuruf tadi. Jika notasi δ: Q × Σ ⟶ Q membingungkanmu, artinya hanya bahwa δ adalah fungsi (mungkin lebih tepat disebut pemetaan) yang menerima dua parameter: state dari Q dan huruf dari Σ. Setelah dipanggil, fungsi mengembalikan state baru. Fungsi transisi kita dapat didefinisikan dengan tabel 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}$$

Jadi, jika kita memanggil δ(q₁, c), kita menerapkan baris ketiga, dan fungsi menjawab dengan state q₂ — sama seperti diagram. Jika kita berada di state q₁ dan inputnya huruf “c”, kita sampai di state q₂. Sebelum mendefinisikan secara formal apa artinya otomaton menerima suatu string, kita gunakan pemahaman intuitif tentang konsep ini dan melihat beberapa contoh lain.

Contoh lain

1. Buatlah otomaton atas alfabet biner, yaitu Σ= {0, 1}, yang hanya menerima string yang diakhiri angka satu. Misalnya, otomaton menerima string 1, 01, 000001, 0101011.

   

   Otomaton kita memiliki dua state — state awal q₀ dan state akhir q₁. Setiap kali inputnya angka 1, kita berpindah ke state akhir q₁ dan tetap di sana. Sebaliknya, jika inputnya angka 0, kita berpindah ke state bukan akhir q₀ dan juga tetap di sana.

2. Konstruksilah otomaton atas alfabet biner yang hanya menerima string dengan huruf pertama yang berbeda dari huruf terakhirnya.

   

   Pada langkah pertama, otomaton langsung terbagi menjadi dua “subotomaton”. Jika string diawali nol, otomaton masuk ke bagian kiri dan tetap di sana; jika diawali satu, otomaton berpindah ke bagian kanan. Selanjutnya, cara kerjanya sudah biasa: jika kita berada di bagian kiri dan inputnya 1, kita berpindah ke state akhir dan tetap di sana. Jika inputnya 0, kita berpindah ke state q₁, yang bukan state akhir.

   Berbeda dengan otomaton sebelumnya, otomaton ini memiliki lebih dari satu state akhir, yaitu F = {q₃, q₄}.

3. Konstruksilah otomaton atas alfabet biner yang hanya menerima string yang tidak memuat dua angka nol berturut-turut.

   

   Otomaton ini menarik karena dua hal. Pertama, otomaton ini menerima string kosong. Kita dapat mencoba memasukkan string kosong ke otomaton, dan otomaton akan menerimanya jika state awal sekaligus merupakan state akhir, seperti pada otomaton ini. Karena string kosong tidak memuat dua angka nol berturut-turut, hasil ini benar. Kedua, semua state pada otomaton ini adalah state akhir. Satu-satunya keadaan ketika otomaton tidak menerima string adalah ketika dari suatu state tidak ada transisi yang bisa diambil. Hal ini terjadi di state q₁, yang tidak memiliki transisi untuk 0, karena dengan transisi tersebut string akan memuat dua angka nol berturut-turut.

4. Konstruksilah otomaton atas alfabet {-,+,.,0,1,…,9} yang hanya menerima string yang menyatakan bilangan, ditulis dengan titik desimal seperti dalam pemrograman. Artinya, bilangan bulat seperti 2, 548, 98263, atau bilangan desimal seperti 5584.48, 3.14, keduanya juga dalam versi bilangan negatif dengan tanda minus -2, -548, -3.14, serta dengan tanda plus yang ditulis secara eksplisit, yaitu +2, +548, +3.14. Selain itu, bilangan 0.123 juga harus dapat ditulis sebagai .123 saja (tanpa nol di depan), termasuk dengan kedua tanda tersebut. Kita gunakan notasi bantu: alih-alih menuliskan sepuluh transisi untuk sepuluh angka, kita gunakan simbol N.

   

5. Konstruksilah otomaton atas alfabet biner yang hanya menerima string berbentuk 0ⁿ1ⁿ, artinya string diawali sejumlah angka nol, lalu diikuti angka satu yang banyaknya sama. Contoh string seperti itu adalah 0011, 00001111, 01.

   Otomaton seperti itu tidak dapat dibuat, karena tidak ada tempat untuk “mengingat” banyaknya angka nol. Kita harus membuat beberapa “subotomaton” seperti pada contoh kedua, tetapi banyaknya “subotomaton” tersebut harus tak hingga, satu untuk setiap nilai n.

Formalisasi komputasi otomaton

Kita sudah mendefinisikan otomaton hingga secara formal. Selanjutnya, kita masih perlu mendefinisikan apa sebenarnya yang dilakukan otomaton, yaitu komputasi otomaton.

Konfigurasi otomaton: Pasangan ⟨q, w⟩ ∈ Q × Σ^∗ disebut konfigurasi otomaton, dengan q state saat ini tempat otomaton berada dan w bagian string yang belum dibaca. Σ^∗ menyatakan penutup alfabet Σ, yaitu himpunan semua string yang dapat disusun dari huruf-huruf alfabet Σ. Penutup ini juga memuat string kosong, yang dilambangkan dengan ε.

Jika ada otomaton ⟨Q, Σ, δ, q₀, F⟩ dan kita ingin menerima string w, otomaton berada pada konfigurasi awal ⟨q₀, w⟩. Jika kita kembali ke otomaton

dan ingin menerima string w = abbc, konfigurasi awalnya adalah ⟨q₀, abbc⟩.

Langkah komputasi didefinisikan sebagai relasi ↦ antara himpunan (Q × Σ^∗) × (Q × Σ^∗), yaitu antara konfigurasi-konfigurasi otomaton. Misalkan w = w₀w₁… w_n menyatakan bagian string w yang belum dibaca. Pasangan ⟨q₁, w₀w₁… w_n⟩ dan ⟨q₂, w₁… w_n⟩ dikatakan berada dalam relasi ↦, ditulis

$$⟨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 ke contoh kita, konfigurasi awalnya adalah ⟨q₀, abbc⟩. Dari diagram terlihat bahwa untuk input “a” kita dapat berpindah ke state q₁. Jadi, kita dapat menulis

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

karena berlaku δ(q₀, a) = q₁. Dengan begitu, kita telah melakukan satu langkah komputasi — kita melihat ke state mana kita harus berpindah untuk input tersebut (= huruf pertama dari bagian string yang belum dibaca), berpindah ke sana, lalu menghapus huruf pertama dari bagian string yang belum dibaca. Hasilnya adalah konfigurasi baru.

Penutup refleksif dan transitif dari relasi langkah komputasi dilambangkan dengan ↦ ^∗. Jadi, jika kita menulis K₁ ↦ ^∗ K₂, dengan K₁, K₂ konfigurasi otomaton, artinya dari konfigurasi K₁ kita dapat mencapai konfigurasi K₂ melalui beberapa langkah komputasi. Dengan kata lain, ada barisan konfigurasi berhingga sedemikian sehingga:

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

Misalnya, pada otomaton kita berlaku ⟨q₀, abbc⟩ ↦ ^∗ ⟨q₁,bc⟩, karena setelah dua langkah komputasi tersisa string “bc” dan kita berada di state q₁. Artinya, ada barisan konfigurasi berikut:

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

Otomaton menerima string w jika dan hanya jika ada q_f ∈ F sedemikian sehingga $$⟨q_0,w⟩{\mapsto }^{\ast }⟨q_f,\epsilon ⟩$$ Artinya, otomaton menerima string w jika dan hanya jika ada barisan langkah komputasi yang pada akhirnya seluruh string sudah dibaca dan kita berada di state akhir otomaton. Fakta bahwa seluruh string sudah dibaca dinyatakan dengan ε, yaitu string kosong, di tempat string pada konfigurasi. Otomaton kita menerima string abbc karena ada barisan konfigurasi berikut:

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

dan state q₂ adalah state akhir, q₂ ∈ F.

Bahasa yang diterima otomaton adalah himpunan semua string yang diterima otomaton. Bahasa otomaton A dilambangkan dengan L(A). Jadi, berlaku L(A) ⊆ Σ^∗ dan

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

Bahasa reguler adalah bahasa yang diterima oleh suatu otomaton hingga.

Dua otomaton hingga ekuivalen jika keduanya menerima bahasa yang sama. Jadi, otomaton A₁ dan A₂ ekuivalen jika berlaku L(A₁) = L(A₂).

Sumber

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