ADVANCED THEORY OF COMPUTING

Nota 2.3: Nondeterministic Finite Automata (NFA) 1. Apakah NFA? NFA ialah mesin dengan bilangan state yang terhingga. Mesin membaca rentetan input untuk menentukan sama ada rentetan itu diterima atau ditolak. Nondeterministic bermaksud satu state dengan simbol input yang sama boleh mempunyai beberapa state destinasi. Ada juga pasangan state dan simbol yang langsung tiada transisi. Semasa menelusuri input, kita mengambil kira semua kemungkinan laluan. Kita tidak memilih satu laluan sahaja lalu mengabaikan laluan lain. 2. Perbezaan asas DFA dan NFA • DFA: setiap pasangan state dan simbol input mempunyai tepat satu state destinasi. • NFA: setiap pasangan state dan simbol input boleh mempunyai sifar, satu atau beberapa state destinasi. • DFA menghasilkan satu state selepas input diproses. • NFA menghasilkan set semua state yang boleh dicapai selepas input diproses. • NFA menerima input jika sekurang-kurangnya satu laluan menerima seluruh input. NFA dan DFA mempunyai kuasa pengecaman bahasa yang sama: kedua-duanya mengenali bahasa regular. NFA boleh memberikan gambaran mesin yang lebih ringkas bagi sesetengah bahasa. 3. Definisi formal M = (Q, Σ, δ, q₀, F) Baca: “Mesin M ditakrifkan oleh Q, sigma, delta, q kosong dan F.” • Q: set semua state yang terhingga. • Σ: set simbol input. • δ: fungsi transisi. • q₀: initial state, iaitu satu ahli Q. • F: set accepting states, iaitu subset Q. Lima komponen ini sama namanya seperti DFA. Perbezaan utama ialah fungsi transisi NFA menghasilkan SET state. 4. Cara membaca fungsi transisi NFA Bagi NFA tanpa transisi λ: δ : Q × Σ → P(Q) Baca: “Delta ialah fungsi daripada Q silang sigma kepada set kuasa Q.” P(Q), juga ditulis 2^Q, ialah set semua subset Q. Oleh itu, hasil transisi boleh berupa set kosong, satu state dalam kurungan set, atau beberapa state. Contohnya, jika Q = {q₀,q₁}, maka: P(Q) = {∅, {q₀}, {q₁}, {q₀,q₁}}. δ(q₁,a) = {q₄,q₅} Baca: “Apabila berada di q satu dan membaca a, state destinasi yang mungkin ialah q empat dan q lima.” δ(q₀,b) = ∅ Baca: “Apabila berada di q kosong dan membaca b, tiada state destinasi.” ∅ bermaksud set kosong. Laluan itu tidak boleh meneruskan pembacaan simbol tersebut. 5. Cara membaca graf NFA • Bulatan ialah state. • Panah masuk dari luar menandakan initial state. • Bulatan berganda menandakan accepting state. • Label pada panah menentukan simbol input yang dibaca. • Jika dua panah berlabel a keluar daripada state yang sama, kedua-dua destinasi perlu diambil kira selepas membaca SATU a. • Tiada panah yang sepadan bermaksud laluan itu tersekat. Set kosong bukan trap state. Set kosong bermaksud tiada kemungkinan state yang tinggal. Trap state pula ialah state sebenar pada graf. 6. Contoh percabangan daripada nota Gunakan transisi berikut untuk contoh aa: q₀ —a→ q₁ q₁ —a→ q₄ q₁ —a→ q₅ Diberi F = {q₀,q₅}. Mula: {q₀} Baca a pertama: {q₁} Baca a kedua: {q₄,q₅} Maka: δ*(q₀,aa) = {q₄,q₅} Baca: “Bermula di q kosong, selepas membaca seluruh aa, semua state yang boleh dicapai ialah q empat dan q lima.” Ada dua kemungkinan laluan: • q₀ —a→ q₁ —a→ q₄ • q₀ —a→ q₁ —a→ q₅ Input aa diterima kerana laluan kedua berakhir di q₅, iaitu accepting state. Laluan pertama tidak menerima, tetapi itu tidak membatalkan laluan yang menerima. 7. Fungsi transisi lanjutan δ* δ* : Q × Σ* → P(Q) Baca: “Delta bintang ialah fungsi daripada Q silang sigma bintang kepada set kuasa Q.” δ memproses satu simbol. δ* memproses seluruh rentetan, termasuk rentetan kosong. Untuk memproses simbol seterusnya, cari transisi daripada SETIAP state semasa, kemudian gabungkan semua hasil. State yang sama ditulis sekali sahaja. Susunan ahli set tidak penting: {q₄,q₅} = {q₅,q₄}. Bagi NFA tanpa transisi λ: δ*(q₀,λ) = {q₀}. 8. Menentukan penerimaan L(M) = {w ∈ Σ* : δ*(q₀,w) ∩ F ≠ ∅} Baca: “Bahasa mesin M ialah set semua rentetan w dalam sigma bintang sedemikian sehingga set state yang dicapai selepas membaca w mempunyai sekurang-kurangnya satu ahli yang sama dengan F.” • ∈: ialah ahli. • ∩: persilangan, iaitu ahli yang sama dalam dua set. • ≠ ∅: bukan set kosong. Contoh: δ*(q₀,aa) = {q₄,q₅} F = {q₀,q₅} {q₄,q₅} ∩ {q₀,q₅} = {q₅} Persilangan tidak kosong, maka aa diterima. Tidak perlu semua state hasil berada dalam F. Cukup sekurang-kurangnya satu. 9. Input mesti habis Sampai di accepting state ketika masih ada input belum menjamin penerimaan. Contohnya, selepas membaca aa, mesin mungkin berada di q₄ atau q₅. Jika input sebenar ialah aab, simbol b masih perlu dibaca. Jika q₄ dan q₅ tiada transisi b, kedua-dua laluan tersekat: δ*(q₀,aab) = ∅. Maka aab ditolak, walaupun satu laluan pernah sampai di accepting state selepas aa. 10. Pengenalan kepada transisi λ Sesetengah nota menggunakan istilah NFA untuk merangkumi mesin dengan transisi λ. Mesin ini juga dinamakan λ-NFA atau ε-NFA. Transisi λ membolehkan mesin bergerak tanpa menggunakan simbol input. λ bukan huruf tambahan dalam alphabet Σ. Bagi mesin dengan λ-moves: δ : Q × (Σ ∪ {λ}) → P(Q). Contoh dalam nota turut mempunyai: q₁ —b→ q₂ q₂ —λ→ q₃ q₃ —λ→ q₀ Selepas membaca ab: q₀ —a→ q₁ —b→ q₂. Kemudian mesin boleh ke q₃ dan q₀ tanpa membaca huruf tambahan: q₂ —λ→ q₃ —λ→ q₀. Oleh itu: δ*(q₀,ab) = {q₂,q₃,q₀}. Input ab diterima kerana q₀ ialah ahli F dalam contoh ini. Penerangan terperinci tentang λ-closure dan pemprosesan λ-moves disambung dalam tajuk 2.4. 11. Kesilapan yang perlu dielakkan • Jangan pilih satu cabang sahaja; ambil kira semua kemungkinan. • Dua panah berlabel a tidak bermaksud membaca aa. Setiap laluan menggunakan satu a untuk transisi itu. • Jangan tentukan penerimaan sebelum seluruh input habis. • Jangan anggap state terakhir mesti satu sahaja; hasil NFA ialah set state. • Jangan keliru ∅ dengan λ: ∅ ialah set kosong, λ ialah rentetan kosong. • Status accepting bergantung pada bulatan berganda atau set F, bukan nama state. 12. Bahasa yang Diterima oleh NFA — Contoh Nota Bahasa L(M) ialah SET SEMUA rentetan yang diterima oleh mesin M, bukan sekadar satu contoh input yang diterima. Untuk contoh muka surat 68–76, gunakan mesin berikut: • Q = {q₀,q₁,q₂,q₃,q₄,q₅} • Σ = {a,b} • Initial state: q₀ • Accepting states: F = {q₀,q₅} Transisinya: • q₀ —a→ q₁ • q₁ —a→ q₄ • q₁ —a→ q₅ • q₁ —b→ q₂ • q₂ —λ→ q₃ • q₃ —λ→ q₀ Transisi lain yang tidak dilukis dianggap tiada. Khususnya, q₄ dan q₅ tiada panah keluar. Penting: nama state dalam contoh ini tidak mempunyai fungsi yang sama seperti graf DFA abba. Di sini q₅ ialah accepting state, bukan trap state. 13. Cara Membaca Formula Penerimaan NFA L(M) = {w ∈ Σ* : δ*(q₀,w) ∩ F ≠ ∅} Baca: “Bahasa mesin M ialah set semua rentetan w dalam sigma bintang sedemikian sehingga set state yang dicapai selepas membaca seluruh w mempunyai sekurang-kurangnya satu ahli yang sama dengan set accepting states F.” • δ*(q₀,w): semua state yang boleh dicapai selepas seluruh w dibaca, termasuk pergerakan λ yang mungkin. • ∩ F: cari state yang turut berada dalam F. • ≠ ∅: hasil persilangan bukan set kosong. Satu laluan yang menerima sudah mencukupi. Input ditolak hanya apabila tiada laluan yang menerima seluruh input. 14. Contoh aa — Diterima Mula: {q₀} Baca a pertama: {q₁} Baca a kedua: {q₄,q₅} δ*(q₀,aa) = {q₄,q₅} Semak accepting states: {q₄,q₅} ∩ {q₀,q₅} = {q₅} Maka aa ∈ L(M). Baca: “aa ialah ahli bahasa mesin M.” Laluan ke q₄ tidak menerima, tetapi laluan ke q₅ menerima. Oleh itu, seluruh input aa diterima. 15. Contoh ab — Diterima q₀ —a→ q₁ —b→ q₂ Input ab sudah habis di q₂. Mesin masih boleh mengambil transisi λ tanpa menggunakan huruf tambahan: q₂ —λ→ q₃ —λ→ q₀ δ*(q₀,ab) = {q₂,q₃,q₀} Ketiga-tiganya termasuk kerana kita boleh mengambil sifar, satu atau dua transisi λ selepas sampai di q₂. {q₂,q₃,q₀} ∩ {q₀,q₅} = {q₀} Maka ab ∈ L(M). 16. Contoh abaa — Diterima Input: a, b, a, a. • Baca a: q₀ ke q₁. • Baca b: q₁ ke q₂. • Ikut λ: q₂ ke q₃, kemudian ke q₀. Baki input masih aa. • Baca a: q₀ ke q₁. • Baca a terakhir: q₁ ke q₄ atau q₅. δ*(q₀,abaa) = {q₄,q₅} Oleh sebab q₅ ∈ F, maka abaa ∈ L(M). Pembetulan slide 74: Sebelah kanan sepatutnya tertulis “abaa ∈ L(M)”, sepadan dengan input abaa pada sebelah kiri. Rentetan aaba pula ditolak: selepas aa, mesin berada di q₄ atau q₅ dan kedua-duanya tiada transisi b. Input aaba tidak dapat dihabiskan. 17. Contoh aba — Ditolak Selepas ab: {q₂,q₃,q₀} Baca a terakhir: • q₂ tiada transisi a secara langsung. • q₃ tiada transisi a secara langsung. • q₀ mempunyai transisi a ke q₁. Pergerakan λ telah diambil kira dalam set semasa, maka hasilnya: δ*(q₀,aba) = {q₁} {q₁} ∩ {q₀,q₅} = ∅ Maka aba ∉ L(M). Baca: “aba bukan ahli bahasa mesin M.” Input sudah habis, tetapi tiada kemungkinan state akhir yang accepting. 18. Rentetan Kosong λ — Diterima Mesin boleh kekal di initial state tanpa membaca apa-apa. Dalam contoh ini, tiada transisi λ keluar dari q₀: δ*(q₀,λ) = {q₀} Oleh sebab q₀ ∈ F, rentetan kosong diterima: λ ∈ L(M). Ini berlaku kerana q₀ ialah accepting state, bukan semata-mata kerana ia initial state. 19. Daripada Contoh kepada Seluruh Bahasa Perhatikan satu pusingan: q₀ —a→ q₁ —b→ q₂ —λ→ q₃ —λ→ q₀ Satu pusingan membaca ab dan membawa mesin semula ke q₀. Oleh sebab q₀ accepting, mesin menerima: λ, ab, abab, ababab, ... Mesin boleh membuat sifar atau beberapa pusingan ab, kemudian mengambil laluan aa ke accepting state q₅. Maka turut diterima: aa, abaa, ababaa, abababaa, ... Selepas sampai di q₅, tiada input tambahan boleh dibaca kerana q₅ tiada panah keluar. Oleh itu, semua rentetan yang diterima mempunyai salah satu bentuk: • (ab)ⁿ, dengan n ≥ 0. • (ab)ⁿaa, dengan n ≥ 0. 20. Rumusan Bahasa yang Betul L(M) = { (ab)ⁿ : n ≥ 0 } ∪ { (ab)ⁿaa : n ≥ 0 } Bentuk ringkas yang setara: L(M) = {ab}* ∪ {ab}*{aa} Atau: L(M) = {ab}*({λ} ∪ {aa}) Dalam notasi ungkapan regular: (ab)*(λ ∪ aa) Cara baca: “Ulang pasangan ab sifar kali atau lebih, kemudian berhenti atau tambah aa di hujung.” • Bintang *: sifar ulangan atau lebih. • ∪: gabungan atau pilihan antara dua set. • Penulisan bersebelahan: cantuman rentetan. • Sifar ulangan ab menghasilkan λ. Contoh n: n = 0: λ atau aa n = 1: ab atau abaa n = 2: abab atau ababaa n = 3: ababab atau abababaa Pembetulan slide 76: Formula pada slide ialah {λ} ∪ {ab}*{aa}. Berdasarkan graf dan F = {q₀,q₅}, formula itu tidak menyenaraikan ab, abab dan ulangan ab yang lain, walaupun mesin menerimanya. Gunakan rumusan yang dibetulkan: L(M) = {ab}* ∪ {ab}*{aa}. 21. Semakan Pantas • λ: diterima; kekal di q₀ yang accepting. • a: ditolak; berakhir di q₁. • aa: diterima; salah satu laluan berakhir di q₅. • ab: diterima; transisi λ boleh membawa mesin ke q₀. • aba: ditolak; berakhir di q₁. • abab: diterima; dua pusingan ab kembali ke q₀. • abaa: diterima; satu pusingan ab diikuti aa. • aaba: ditolak; tiada transisi b selepas sampai di q₄ atau q₅. • aaa: ditolak; tiada transisi a keluar dari q₄ atau q₅. Rumusan ini khusus untuk graf contoh tersebut. Untuk NFA lain, tentukan semula initial state, F dan semua transisi sebelum merumuskan L(M).