Perbedaan DFA dan NFA

Finite automata merupakan mesin automata dari bahasa reguler. Seperti yang kita ketahui, finite automata terbagi menjadi 2:

1. Deterministic Finite Automata (DFA) menerima masukan (input) yang hanya memiliki 1 busur keluar.

DFA sendiri merupakan finite automata dengan memiliki 5 tuple yang direpresentasikan sebagai berikut:

Q, himpunan state, contohnya {q0, q1, q2}

Σ, input alphabet, contohnya {a, b}

δ, fungsi transisi

q0, state awal

F, state akhir

2. Non-Deterministic Finite Automata (NFA) menerima masukan (input) dengan memiliki lebih dari 1 busur keluar atau bahkan tidak memiliki busur keluar.

NFA sendiri merupakan finite automata dengan memiliki 5 tuple yang direpresentasikan sebagai berikut:

Q, himpunan state, contohnya {q0, q1, q2}

Σ, input alphabet, contohnya {a, b}

δ, fungsi transisi

q0, state awal

F, state akhir

Perbedaan DFA dan NFA

DFA

• DFA tidak dapat menggunakan transisi string kosong (empty string)
• Dipahami sebagai sebuah mesin
• DFA untuk state selanjutnya bisa ditetapkan dengan jelas
• DFA lebih sulit dibuat
• Waktu yang dibutuhkan untuk mengeksekusi string input lebih sedikit
• Semua DFA merupakan NFA
• DFA membutuhkan lebih banyak ruang (space)

NFA

• NFA dapat menggunakan transisi string kosong (empty string)
• NFA dipahami sebagai beberapa mesin kecil yang melakukan komputasi di waktu bersamaan
• NFA untuk state selanjutnya mempunyai banyak kemungkinan
• NFA lebih mudah dibuat
• Waktu yang dibutuhkan untuk mengeksekusi string input lebih banyak
• Tidak semua NFA adalah DFA
• NFA membutuhkan lebih sedikit ruang (space)