Simulasi automaton tak berketentuan

Jika kita mempunyai automaton tak berketentuan dan mahu menentukan sama ada automaton itu menerima suatu rentetan, kita boleh menukarkannya kepada automaton berketentuan, kita boleh mencubanya dengan apa-apa cara, atau kita boleh menggunakan algoritma yang menyimulasikan kerja NFA.

Prinsip algoritma

Mari kita lihat prinsipnya melalui contoh yang sesuai. Katakan kita mempunyai automaton berikut:

Automaton ini ialah automaton terhingga tak berketentuan yang menerima suatu bahasa. Bahasa yang mana tidak penting buat masa ini. Kita akan melihat rupa pengiraan automaton ini bagi rentetan input 11001. Ideanya begini: kita memproses satu simbol daripada rentetan dan melihat semua keadaan yang boleh dicapai disebabkan peralihan berganda bagi simbol yang sama. Kita ingat semua keadaan itu, dan pada langkah seterusnya kita menganggap bahawa kita berada “dalam semua keadaan itu serentak”. Kemudian kita melihat ke mana kita boleh pergi dari keadaan-keadaan itu.

Jadi, kita mengingat set keadaan tempat kita mungkin berada serta bahagian rentetan yang belum dibaca. Pada mulanya kita mempunyai pasangan ⟨{q₀}, 11001⟩. Kita bermula pada keadaan q₀ (keadaan awal) dan input ialah rentetan 11001. Automaton kelihatan seperti berikut; keadaan tempat kita berada ditonjolkan dengan warna merah dan huruf tebal:

Simbol pertama ialah 1. Dari keadaan q₀ hanya ada satu peralihan bagi simbol 1, jadi kita sampai ke keadaan q₁. Kita ingat pasangan ⟨{q₁}, 1001⟩. Automaton kelihatan seperti berikut:

Kita teruskan. Bahagian rentetan yang belum dibaca ialah 1001, jadi sekali lagi kita mencari peralihan bagi 1. Kali ini ada dua — kembali ke keadaan q₀ dan ke keadaan q₃. Sekarang kita pergi ke kedua-dua keadaan serentak. Kita ingat pasangan ⟨{q₀, q₃}, 001⟩.

Apakah logiknya? Kita tahu bahawa terdapat laluan dari keadaan awal dengan rentetan 11 ke keadaan q₃ dan juga ke keadaan q₀. Kita belum tahu cabang mana yang akan berguna, jadi kita ingat kedua-duanya. Kita teruskan. Input ialah simbol 0. Sekarang kita perlu melihat peralihan dari q₀ dan juga dari q₃. Dari keadaan q₀ terdapat peralihan ke keadaan q₁ dan q₂, dan dari keadaan q₃ terdapat peralihan kembali ke q₁. Kita ambil kira semua keadaan ini dan memperoleh pasangan ⟨{q₁, q₂}, 01⟩:

Namun, langkah ini belum selesai. Kita lihat bahawa dari keadaan q₂ terdapat peralihan epsilon ke keadaan q₄. Kita tahu bahawa peralihan epsilon boleh diikuti “pada bila-bila masa” tanpa membaca aksara seterusnya. Dengan kata lain, tanpa membaca simbol seterusnya daripada rentetan input, kita masih boleh beralih ke keadaan q₄. Oleh itu, kita menambahkan keadaan q₄ kepada keadaan tempat kita mungkin berada: ⟨{q₁, q₂, q₄}, 01⟩. Automaton diwarnakan seperti berikut:

Input seterusnya ialah 0. Kita lihat ke mana kita boleh beralih dari tiga keadaan tempat kita berada. Dari q₁ kita tidak boleh beralih ke mana-mana kerana tiada peralihan bagi 0. Pengiraan dalam cabang ini berakhir. Dari keadaan q₄ kita juga tidak dapat pergi ke mana-mana. Dari keadaan q₂ kita kembali ke keadaan q₂. Namun, oleh sebab terdapat peralihan epsilon dari keadaan q₂ ke keadaan q₄, kita juga boleh sampai ke keadaan q₄. Jadi, dari set keadaan {q₁, q₂, q₄}, bagi simbol 0 kita boleh sampai ke set keadaan {q₂, q₄}, dan kita memperoleh pasangan ⟨{q₂, q₄}, 1⟩:

Akhirnya input ialah simbol 1. Dari keadaan q₂ kita tidak dapat pergi ke mana-mana, jadi pengiraan dalam cabang ini berakhir. Namun, dari keadaan q₄ kita sampai ke keadaan q₃ dan q₅. Kita memperoleh pasangan ⟨{q₃, q₅}, ε⟩:

Kini automaton telah membaca keseluruhan rentetan dan “berada” dalam dua keadaan: q₃, q₅. Oleh sebab sekurang-kurangnya satu daripadanya ialah keadaan akhir, automaton menerima rentetan 11001.

Algoritma

Pertama sekali, kita memerlukan fungsi yang menerima set keadaan sebagai parameter dan mengira keadaan lain yang masih boleh dicapai melalui peralihan epsilon. Inputnya ialah automaton ⟨Q, Σ, δ, q₀, F⟩ dan set keadaan States, manakala outputnya ialah superset bagi keadaan-keadaan ini yang mengandungi semua keadaan yang boleh dicapai melalui peralihan epsilon. Operasi ini dipanggil tutupan epsilon bagi set 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 digunakan dalam fungsi yang menyimulasikan kerja automaton tak berketentuan. Inputnya ialah automaton, rentetan input w = w₁w₂… w_n dan set keadaan tempat automaton sedang berada. Outputnya ialah jawapan YES (ya) atau NO (tidak), bergantung pada sama ada automaton menerima rentetan itu 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}$$

Untuk menyemak sama ada automaton menerima rentetan w, kita memanggil fungsi seperti berikut: 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