Perbezaan antara NFA dan DFA

NFA vs DFA

Teori perhitungan adalah cawangan sains komputer yang menangani masalah bagaimana menyelesaikan masalah menggunakan algoritma. Ia mempunyai tiga cabang, iaitu; teori kerumitan komputasi, teori komputabilitas, dan teori automaton.

Teori automaton atau automata adalah kajian terhadap mesin atau sistem matematik abstrak yang boleh digunakan untuk menyelesaikan masalah pengkomputeran. Automatik terdiri daripada keadaan dan peralihan, dan kerana ia melihat simbol atau huruf input, ia membuat peralihan ke keadaan lain yang mengambil keadaan semasa dan simbol sebagai input.

Teori automaton atau automata mempunyai beberapa kelas termasuk Deterministic Finite Automata (DFA) dan Automated Finite Nite (NFA). Kedua-dua kelas ini adalah fungsi peralihan automata atau automaton.

Dalam peralihan, DFA tidak boleh menggunakan n kosong string, dan ia dapat difahami sebagai satu mesin. Jika rentetan berakhir pada keadaan yang tidak dapat diterima, DFA akan menolaknya. Mesin DFA boleh dibina dengan setiap input dan output.

DFA hanya mempunyai satu peralihan negeri untuk setiap simbol abjad, dan hanya ada satu negeri akhir untuk peralihannya yang bermaksud bahawa bagi setiap watak yang dibaca, terdapat satu keadaan yang sepadan dalam DFA. Adalah lebih mudah untuk memeriksa keahlian dalam DFA tetapi lebih sukar untuk dibina. Backtracking dibenarkan dalam DFA, dan ia memerlukan lebih banyak ruang daripada NFA.

Backtracking tidak selalu dibenarkan dalam NFA. Walaupun ada kemungkinan dalam sesetengah kes, orang lain tidak. Ia lebih mudah untuk membina NFA, dan ia juga memerlukan kurang ruang, tetapi tidak mungkin untuk membina mesin NFA untuk setiap input dan output.

Ia difahami sebagai beberapa mesin kecil yang mengira secara serentak, dan keanggotaan lebih sukar untuk diperiksa. Ia menggunakan Peralihan String Kosong, dan terdapat banyak kemungkinan keadaan seterusnya untuk setiap pasangan simbol negeri dan input. Ia bermula pada keadaan tertentu dan membaca simbol-simbol, dan automaton kemudian menentukan keadaan seterusnya yang bergantung pada input semasa dan peristiwa-peristiwa akibat yang lain. Pada keadaan penerimaannya, NFA menerima rentetan dan menolaknya sebaliknya.

Ringkasan:

1. "DFA" bermaksud "Deterministic Finite Automata" manakala "NFA" bermaksud "Automata Finite Nondeterministic."
2.Adalah fungsi peralihan automata. Dalam DFA keadaan mungkin seterusnya jelas ditetapkan manakala dalam NFA setiap sepasang negeri dan simbol masukan dapat mempunyai banyak kemungkinan keadaan seterusnya.
3.NFA boleh menggunakan peralihan rentetan kosong sementara DFA tidak boleh menggunakan peralihan rentetan kosong.
4.NFA adalah lebih mudah untuk membina sementara ia adalah lebih sukar untuk membina DFA.
5.Backtracking dibenarkan dalam DFA semasa di NFA ia mungkin atau tidak boleh dibenarkan.
6.DFA memerlukan lebih banyak ruang manakala NFA memerlukan kurang ruang.
7. Walaupun DFA boleh difahami sebagai satu mesin dan mesin DFA boleh dibina untuk setiap input dan output, 8.NFA boleh difahami sebagai beberapa mesin kecil yang mengira bersama-sama, dan tidak ada kemungkinan untuk membina mesin NFA untuk setiap input dan output.