- 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
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 NFA DFA tidak dapat menggunakan transisi string kosong (empty string) NFA dapat menggunakan transisi string kosong (empty string) DFA dipahami sebagai sebuah mesin NFA dipahami sebagai beberapa mesin kecil yang melakukan komputasi di waktu bersamaan DFA untuk state selanjutnya bisa ditetapkan dengan jelas NFA untuk state selanjutnya mempunyai banyak kemungkinan DFA lebih sulit dibuat NFA lebih mudah dibuat Waktu yang dibutuhkan untuk mengeksekusi string input lebih sedikit Waktu yang dibutuhkan untuk mengeksekusi string input lebih banyak Semua DFA merupakan NFA Tidak semua NFA adalah DFA DFA membutuhkan lebih banyak ruang (space) NFA membutuhkan lebih sedikit ruang (space)
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 | NFA |
| DFA tidak dapat menggunakan transisi string kosong (empty string) | NFA dapat menggunakan transisi string kosong (empty string) |
| DFA dipahami sebagai sebuah mesin | NFA dipahami sebagai beberapa mesin kecil yang melakukan komputasi di waktu bersamaan |
| DFA untuk state selanjutnya bisa ditetapkan dengan jelas | NFA untuk state selanjutnya mempunyai banyak kemungkinan |
| DFA lebih sulit dibuat | NFA lebih mudah dibuat |
| Waktu yang dibutuhkan untuk mengeksekusi string input lebih sedikit | Waktu yang dibutuhkan untuk mengeksekusi string input lebih banyak |
| Semua DFA merupakan NFA | Tidak semua NFA adalah DFA |
| DFA membutuhkan lebih banyak ruang (space) | NFA membutuhkan lebih sedikit ruang (space) |
No comments:
Post a Comment