Otomaton hingga nondeterministik

Otomaton hingga yang diperkenalkan pada bab-bab sebelumnya (disingkat DFA) selalu deterministik. Artinya, pada setiap saat jelas apa yang akan dilakukan otomaton. Sekarang kita akan melihat konsep yang lebih umum, yaitu otomaton hingga nondeterministik (disingkat NFA). Pada otomaton ini bisa ada beberapa transisi yang berasal dari state yang sama untuk simbol yang sama.

Contoh

Perhatikan diagram otomaton berikut:

Apa yang aneh pada diagram ini? Dari simpul q₀ keluar dua busur untuk simbol 0. Jadi, jika kita mencoba menerima string 001, tampaknya otomaton tidak tahu apakah harus tetap di state q₀ atau mengikuti transisi ke q₁. Otomaton seperti ini disebut nondeterministik.

Determinisme dalam pengertian ini berarti bahwa dalam setiap situasi jelas apa yang akan dilakukan otomaton, tidak ada ruang untuk ketaktunggalan. Otomaton deterministik hanya memiliki satu transisi untuk setiap state dan setiap simbol. Nondeterminisme berarti ketaktunggalan — dari satu state bisa keluar, misalnya, tiga transisi untuk simbol yang sama.

Lalu, bagaimana otomaton memutuskan? Otomaton nondeterministik selalu memilih (kadang dikatakan juga “menebak”) transisi yang membuatnya menerima string, jika hal itu mungkin.

Jika kita memasukkan string 001 ke otomaton, otomaton memiliki pilihan-pilihan berikut untuk memproses string tersebut:

$$\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}$$

ditambah pilihan-pilihan yang tidak membaca seluruh string. Pada pilihan pertama, otomaton terus berada di state q₀, dan hal itu jelas boleh karena aturan transisinya mengizinkan. Pada cabang kedua, otomaton berani berpindah ke state-state lain dan akhirnya sampai di state q₂, yang merupakan state akhir. Pada cabang ini, otomaton menerima string. Otomaton nondeterministik selalu otomatis memilih cabang yang membuatnya menerima string, jika cabang seperti itu ada.

Bagaimana otomaton bisa otomatis memilih cabang yang “menguntungkan”? Kita dapat membayangkan bahwa otomaton nondeterministik menelusuri semua cabang yang mungkin, dan jika menemukan cabang yang menerima string, otomaton menerima string tersebut. Bagaimana otomaton dapat menelusuri semua cabang? Sederhana saja: ketika berada di state yang memiliki n busur keluar untuk simbol saat ini, otomaton menyalin dirinya n kali, dan setiap salinan menempuh jalur yang berbeda. Dengan cara ini, semua kemungkinan ditelusuri satu per satu.

Representasi pohon untuk komputasi otomaton

Kita sedikit memodifikasi otomaton sebelumnya:

Nondeterminisme tetap ada di state pertama. Otomaton sebelumnya menerima semua string yang diakhiri 01. Otomaton hasil modifikasi ini menerima semua string yang memuat substring 01. Jadi, otomaton ini menerima, misalnya, string 101 atau 0101. Semua cabang komputasi dapat dengan mudah divisualisasikan dengan pohon. Misalnya, untuk string 01010 pohonnya dapat terlihat seperti ini:

Pada awalnya, kita berada di state awal q₀. Inputnya adalah string 01010, dan karakter pertama yang belum dibaca adalah 0. Dari state q₀ keluar dua transisi untuk simbol 0, yaitu ke state q₀ dan q₁. Jadi, pohon pada simpul ini memiliki dua anak: q₀ dan q₁. Selanjutnya, kita membaca simbol 1. Di sini tidak ada ketaktunggalan, kita berpindah ke state q₀ dan q₂. Kemudian kita membaca karakter 0; pada cabang kiri kembali terjadi ketaktunggalan, sehingga komputasi kita bagi menjadi dua cabang lagi. Pada salah satunya, kita kembali tetap di q₀, dan pada yang lain kita berpindah ke q₁. Begitu seterusnya.

Perhatikan bahwa ada dua cabang yang berakhir di state q₂, yaitu state akhir. Ada dua cabang komputasi yang membuat otomaton dapat menerima string tersebut. Jadi, otomaton ini menerima string 01010. Kita dapat mencoba membuat pohon serupa untuk string 1000.

Komputasi tetap berada di state q₀ atau berpindah ke state q₁, tetapi dari sana tidak ada tujuan lagi, karena input berikutnya hanya angka nol, sedangkan state q₁ hanya memiliki transisi untuk simbol 1. Tidak ada cabang komputasi yang berakhir di state akhir, sehingga otomaton tidak menerima string 1000.

Transisi epsilon

Pada otomaton nondeterministik, kita juga dapat menggunakan transisi epsilon. Transisi ini dapat dilakukan apa pun simbol inputnya, tanpa membaca simbol apa pun dari string. Bagaimana kita menulis otomaton nondeterministik yang menerima string kosong, semua string yang hanya tersusun atas angka satu, dan string berbentuk (10)ⁿ, yaitu 10, 1010, …?

Otomaton kita bagi menjadi dua “subotomaton”. Bagian atas bertugas mengenali string yang tersusun atas angka 1, sedangkan bagian bawah menangani string berbentuk (10)ⁿ. Kita coba menerima string 111. Pada awalnya, otomaton berada di state q₀ dengan input string 111. Karena tersedia transisi epsilon, otomaton dapat memilih untuk berpindah ke state q₁ atau q₂, sesuai kebutuhannya. Terlihat bahwa yang menguntungkan adalah berpindah ke state q₁. Otomaton pun berpindah ke sana, dan inputnya masih tetap string 111! Baru pada saat ini otomaton mulai membaca simbol dari string dan berpindah dari state q₁ kembali ke q₁, sampai seluruh string terbaca dan diterima.

Jika kita mencoba menerima 1010, pada awalnya otomaton berpindah ke state q₂, baru dari sana mulai memproses simbol, dan string ini juga diterima.

Untuk string 1100, apa pun yang dilakukan otomaton, string tersebut tidak dapat diterima.

Transisi epsilon dan nondeterminisme dalam banyak hal mempermudah pekerjaan kita. Misalnya, bukti bahwa gabungan bahasa reguler juga merupakan bahasa reguler dapat ditulis jauh lebih sederhana dengan transisi epsilon daripada dengan otomaton hingga deterministik. Dalam bukti tersebut, kita memiliki contoh otomaton berikut

dan

lalu kita mengonstruksi otomaton hingga deterministik yang menerima gabungan kedua bahasa. Dengan transisi epsilon, otomaton seperti itu dapat dikonstruksi sebagai berikut:

Singkatnya, kita menambahkan state awal baru, dan dari state ini dibuat dua transisi epsilon ke state awal kedua otomaton semula. Selesai. Otomaton memutuskan secara nondeterministik apakah akan mencoba menerima string dengan “subotomaton” pertama atau kedua.

Definisi otomaton nondeterministik

Kita sudah melihat perbedaan antara otomaton hingga deterministik dan nondeterministik, tinggal memformalkannya. Otomaton hingga deterministik kita definisikan sebagai lima-tupel ⟨Q, Σ, δ, q₀, F⟩, dengan Q himpunan state, Σ alfabet, δ fungsi transisi, q₀ state awal, dan F himpunan state akhir. Satu-satunya yang berubah pada definisi otomaton nondeterministik adalah definisi fungsi transisinya.

Pada versi deterministik, fungsi untuk pemanggilan δ(q, w) hanya dapat mengembalikan satu state, sedangkan pada versi nondeterministik fungsi tersebut dapat mengembalikan beberapa state — jika untuk satu simbol terdefinisi beberapa transisi. Karena kita juga perlu mendefinisikan transisi epsilon, himpunan Σ ∪ {ε} kita lambangkan dengan Σ_ε, yaitu Σ_ε = Σ ∪ {ε}. Jadi, fungsi δ didefinisikan sebagai

$$\delta :Q\times {\mathrm{\Sigma }}_{\epsilon }\to 2^Q$$

Lambang 2^Q menyatakan himpunan kuasa, yaitu himpunan semua himpunan bagian dari Q. Formalisasi komputasinya sangat mirip dengan otomaton hingga. Konfigurasi otomaton kembali berupa pasangan ⟨q, w⟩ ∈ Q × Σ^∗. Langkah komputasi ↦ adalah relasi pada himpunan konfigurasi sedemikian sehingga

$$⟨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₀). Di kalimat inilah perbedaan terbesarnya. Pada otomaton deterministik, syarat ini kita tulis sebagai q_j = δ(q_i, w₀), karena fungsi δ selalu mengembalikan satu state. Versi nondeterministik fungsi transisi mengembalikan himpunan state, sehingga digunakan simbol ∈. Penutup refleksif dan transitif relasi ini kembali dilambangkan dengan ↦ ^∗. Otomaton dikatakan menerima string w jika dan hanya jika ada q_f ∈ F sedemikian sehingga

$$⟨q_0,w⟩{\mapsto }^{\ast }⟨q_f,\epsilon ⟩.$$

Sumber

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