Perbezaan antara NFA dan DFA

NFA vs DFA

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

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

Teori Automaton atau Automata mempunyai beberapa kelas yang termasuk automata terhingga (DFA) dan nondeterministik terhingga automata (NFA). Kedua -dua kelas ini adalah fungsi peralihan automata atau automaton.

Dalam peralihan, DFA tidak dapat menggunakan rentetan kosong, dan dapat difahami sebagai satu mesin. Sekiranya 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 keadaan terakhir untuk peralihannya yang bermaksud bahawa bagi setiap watak yang dibaca, terdapat satu keadaan yang sepadan dalam DFA. 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 di NFA. Walaupun ada kemungkinan dalam beberapa kes, pada yang lain tidak. Lebih mudah untuk membina NFA, dan ia juga memerlukan ruang yang kurang, tetapi tidak mungkin untuk membina mesin NFA untuk setiap input dan output.

Difahamkan sebagai beberapa mesin kecil yang mengira secara serentak, dan keahlian dapat lebih sukar untuk diperiksa. Ia menggunakan peralihan rentetan kosong, dan terdapat banyak kemungkinan keadaan seterusnya untuk setiap pasangan keadaan dan simbol input. Ia bermula pada keadaan tertentu dan membaca simbol -simbol, dan automaton kemudian menentukan keadaan seterusnya yang bergantung pada input semasa dan peristiwa akibat lain. Pada keadaan yang diterima, NFA menerima rentetan dan menolaknya sebaliknya.

Ringkasan:

1."DFA" bermaksud "automata terhingga deterministik" manakala "NFA" bermaksud "Automata terhingga nondeterministik."
2.Kedua -duanya adalah fungsi peralihan automata. Di DFA keadaan seterusnya yang mungkin ditetapkan dengan jelas manakala di NFA setiap pasangan keadaan dan simbol input boleh mempunyai banyak keadaan seterusnya.
3.NFA boleh menggunakan peralihan rentetan kosong sementara DFA tidak dapat menggunakan peralihan rentetan kosong.
4.NFA lebih mudah dibina sementara lebih sukar untuk membina DFA.
5.Backtracking dibenarkan di DFA semasa di NFA ia mungkin atau mungkin tidak dibenarkan.
6.DFA memerlukan lebih banyak ruang sementara NFA memerlukan ruang yang kurang.
7.Walaupun DFA dapat difahami sebagai satu mesin dan mesin DFA boleh dibina untuk setiap input dan output, 8.NFA dapat difahami sebagai beberapa mesin kecil yang mengira bersama, dan tidak ada kemungkinan untuk membina mesin NFA untuk setiap input dan output.