Perbezaan Antara NFA dan DFA Perbezaan Antara

NFA vs DFA

Teori perhitungan adalah cabang 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 mesin atau sistem matematik abstrak yang boleh digunakan untuk menyelesaikan masalah pengiraan. Automatik terdiri daripada negeri dan peralihan, dan kerana ia melihat simbol atau surat input, ia membuat peralihan ke negeri lain yang mengambil keadaan semasa dan simbol sebagai input.

Automatik atau teori automata mempunyai beberapa kelas yang termasuk Deterministic Finite Automata (DFA) dan Nondeterministic Finite Automata (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 bukan keadaan yang boleh 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 bagi setiap sepasang simbol input dan negeri. 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. Kedua-duanya adalah fungsi peralihan automata. Dalam DFA keadaan mungkin seterusnya jelas ditetapkan manakala dalam NFA setiap sepasang negeri dan simbol masukan dapat memiliki banyak kemungkinan keadaan seterusnya.

3. NFA boleh menggunakan peralihan rentetan kosong sementara DFA tidak boleh menggunakan peralihan rentetan kosong.

4. NFA lebih mudah untuk dibina sementara ia 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.