Perbedaan DFA dan NFA, jika DFA state diberi input, selanjutnya tepat menuju 1 state, berbeda dengan NFA bisa saja menuju ke beberapa state selanjutnya.
Berbagai perbedaan DFA dan NFA lain, terkait ruang (space) dan eksekusi string yang dilakukan.
Deterministic Finite Automata (DFA) menerima masukan (input) yang hanya memiliki 1 busur keluar
Deterministic Finite Automata (DFA) sering dikenal juga sebagai Deterministic Finite-State Machine (DFSM) dan Deterministic Finite-State Automaton (DFSA).
Non-Deterministic Finite Automata (NFA) menerima masukan (input) dengan memiliki lebih dari 1 busur keluar atau bahkan tidak memiliki busur keluar.
Non-Deterministic Finite Automata (NFA) sering dikenal juga sebagai Non-Deterministic Finite-State Machine (NFSM) dan Non-Deterministic Finite-State Automaton (NFSA).
Perbedaan DFA dan NFA
Pada intinya, paling mendasar perbedaan DFA dan NFA, jika DFA apabila state diberi input, maka state akan selalu tepat menuju 1 state. Berbeda dengan NFA, jika state diberi input, mungkin saja bisa menuju ke beberapa state selanjutnya.
Sementara itu, berikut ini beberapa perbedaan DFA dan NFA yang disajikan dalam tabel:
DFA
DFA tidak dapat menggunakan transisi string kosong (empty string)
DFA 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)
No comments:
Post a Comment