Simulasi otomaton nondeterministik

Jika kita memiliki otomaton nondeterministik dan ingin mengetahui apakah otomaton tersebut menerima suatu string, kita dapat mengonversinya menjadi otomaton deterministik, mencobanya dengan cara tertentu, atau menggunakan algoritma yang menyimulasikan kerja NFA.

Prinsip algoritma

Prinsipnya akan kita tunjukkan dengan contoh yang sesuai. Misalkan ada otomaton berikut:

Ini adalah otomaton hingga nondeterministik yang menerima suatu bahasa. Bahasa apa, sama sekali tidak penting sekarang. Kita akan melihat seperti apa komputasi otomaton ini untuk string input 11001. Idenya begini: kita memproses satu simbol dari string dan melihat ke mana saja kita dapat pergi berkat adanya beberapa transisi untuk simbol yang sama. Semua state tersebut kita ingat, dan pada langkah berikutnya kita anggap bahwa kita berada “di semua state itu sekaligus”, lalu kita cari ke mana saja kita dapat melanjutkan dari state-state tersebut.

Jadi, kita mengingat himpunan state tempat kita mungkin berada dan bagian string yang belum dibaca. Pada awalnya, kita memiliki pasangan ⟨{q₀}, 11001⟩. Kita mulai dari state q₀ (state awal), dan inputnya adalah string 11001. Otomatonnya terlihat seperti ini; state tempat kita berada ditandai dengan warna merah dan cetak tebal:

Simbol pertama adalah 1. Dari state q₀ hanya ada satu transisi untuk simbol 1, sehingga kita sampai di state q₁. Kita ingat pasangan ⟨{q₁}, 1001⟩. Otomatonnya terlihat seperti ini:

Kita lanjutkan. Bagian string yang belum dibaca berbentuk 1001, jadi kita kembali mencari transisi untuk 1. Kali ini ada dua — kembali ke state q₀ dan ke state q₃. Sekarang kita pergi ke kedua state sekaligus. Jadi, kita ingat pasangan ⟨{q₀, q₃}, 001⟩.

Apa logikanya? Kita tahu bahwa ada jalur dari state awal dengan string 11 ke state q₃ maupun ke state q₀. Kita belum tahu cabang mana yang akan berguna, jadi kita ingat saja keduanya. Kita lanjutkan. Inputnya adalah simbol 0. Sekarang kita harus memperhatikan transisi dari q₀ maupun transisi dari q₃. Dari state q₀ ada transisi ke state q₁ dan q₂, sedangkan dari state q₃ ada transisi kembali ke q₁. Semua state ini kita masukkan, sehingga diperoleh pasangan ⟨{q₁, q₂}, 01⟩:

Namun, langkah ini belum selesai. Terlihat bahwa dari state q₂ ada transisi epsilon ke state q₄. Kita tahu bahwa transisi epsilon dapat “diambil kapan saja” tanpa membaca karakter berikutnya. Dengan kata lain, tanpa membaca simbol berikutnya dari string input, kita masih dapat berpindah ke state q₄. Jadi, state q₄ kita tambahkan ke state-state tempat kita mungkin berada: ⟨{q₁, q₂, q₄}, 01⟩. Otomatonnya kita warnai seperti ini:

Input berikutnya adalah 0. Kita lihat ke mana kita dapat berpindah dari ketiga state tempat kita berada. Dari q₁ kita tidak dapat berpindah ke mana pun karena tidak ada transisi untuk 0. Komputasi pada cabang ini berakhir. Dari state q₄ kita juga tidak dapat ke mana-mana. Dari state q₂ kita kembali ke state q₂. Namun, karena dari state q₂ ada transisi epsilon ke state q₄, kita juga dapat sampai di state q₄. Jadi, dari himpunan state {q₁, q₂, q₄} untuk simbol 0 kita dapat sampai di himpunan state {q₂, q₄}, dan diperoleh pasangan ⟨{q₂, q₄}, 1⟩:

Terakhir, inputnya adalah simbol 1. Dari state q₂ kita tidak dapat ke mana pun, sehingga komputasi pada cabang ini berakhir. Namun, dari state q₄ kita dapat sampai di state q₃ dan q₅. Diperoleh pasangan ⟨{q₃, q₅}, ε⟩:

Sekarang otomaton sudah membaca seluruh string dan “berada” di dua state: q₃, q₅. Karena setidaknya salah satunya adalah state akhir, otomaton menerima string 11001.

Algoritma

Pertama, kita memerlukan fungsi yang menerima himpunan state sebagai parameter dan menghitung state mana saja yang masih dapat dicapai melalui transisi epsilon. Jadi, inputnya adalah otomaton ⟨Q, Σ, δ, q₀, F⟩ dan himpunan state States, sedangkan outputnya adalah superhimpunan dari state-state tersebut, berisi state yang dapat dicapai melalui transisi epsilon. Operasi ini disebut penutup epsilon dari himpunan States.

$$\begin{array}{r}\\ & \mathbf{Function}EpsilonClosure(⟨Q,\mathrm{\Sigma },\delta ,q_0,F⟩,States)\\ & NextStates\leftarrow \mathrm{\varnothing }\\ & \mathbf{ForEach}q\in States\mathbf{Do}\\ & NextStates\leftarrow NextStates\cup \left\{q\right\}\cup \delta (q,\epsilon )\\ & \mathbf{EndFor}\\ & \\ & \mathbf{If}NextStates\setminus States=\mathrm{\varnothing }\mathbf{Do}\\ & \mathbf{Return}States\\ & \mathbf{Else}\\ & \mathbf{Return}EpsilonClosure(⟨Q,\mathrm{\Sigma },\delta ,q_0,F⟩,NextStates)\\ & \mathbf{EndIf}\\ & \mathbf{EndFunction}\\ & \end{array}$$

Fungsi ini kita gunakan dalam fungsi yang menyimulasikan kerja otomaton nondeterministik. Inputnya adalah otomaton, string input w = w₁w₂… w_n, dan himpunan state tempat otomaton saat ini berada. Outputnya adalah jawaban Ya atau Tidak, bergantung pada apakah otomaton menerima string tersebut atau tidak.

$$\begin{array}{r}\\ & \mathbf{Function}ComputeNFA(⟨Q,\mathrm{\Sigma },\delta ,q_0,F⟩,w,States)\\ & \mathbf{If}w=ϵ\mathbf{Do}\\ & \mathbf{If}States\cap F\ne \mathrm{\varnothing }\mathbf{Do}\\ & \mathbf{Return}\text{YES}\\ & \mathbf{Else}\\ & \mathbf{Return}\text{NO}\\ & \mathbf{EndIf}\\ & \mathbf{EndIf}\\ & NextStates\leftarrow \mathrm{\varnothing }\\ & \mathbf{ForEach}q\in States\mathbf{Do}\\ & NextStates\leftarrow NextStates\cup \delta (q,w_1)\\ & \mathbf{EndFor}\\ & NextStates\leftarrow EpsilonClosure(⟨Q,\mathrm{\Sigma },\delta ,q_0,F⟩,NextStates)\\ & \mathbf{Return}ComputeNFA(⟨Q,\mathrm{\Sigma },\delta ,q_0,F⟩,w_2{w}_3\dots w_n,NextStates)\\ & \mathbf{EndFunction}\\ & \end{array}$$

Jika ingin memeriksa apakah otomaton menerima string w, kita panggil fungsinya seperti ini: ComputeNFA(⟨Q, Σ, δ, q₀, F⟩, w, EpsilonClosure(⟨Q, Σ, δ, q₀, F⟩, {q₀})).

Sumber

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