Perbedaan DFA dan NFA

Perbedaan DFA dan NFA

  • 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.

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

  1. Deterministic Finite Automata (DFA)
  2. Non-Deterministic Finite Automata (NFA)

Baik itu DFA maupun NFA, memiliki ciri-ciri atau karakteristik yang berbeda.

Berikut ini beberapa perbedaan DFA dan NFA, dengan disertai pengertian dan contoh dari masing-masing DFA dan NFA.

Deterministic Finite Automata (DFA)

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).

DFA diperkenalkan oleh Warren McCulloch dan Walter Pitts sebagai peneliti pertama yang memperkenalkan konsep yang mirip dengan finite automata di tahun 1943.

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

Contoh DFA

  • Q = {q0, q1, q2}
  • ∑ = {0, 1}
  • q0 = {q0}
  • F = {q2}
Contoh DFA
Contoh DFA

Non-Deterministic Finite Automata (NFA)

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).

NFA diperkenalkan pada tahun 1959 oleh Michael O. Rabin dan Dana Scott.

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

Contoh NFA

  • Q = {q0, q1, q2}
  • ∑ = {0, 1}
  • q0 = {q0}
  • F = {q2}
Contoh NFA
Contoh NFA

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:

DFANFA
DFA tidak dapat menggunakan transisi string kosong (empty string)NFA dapat menggunakan transisi string kosong (empty string)
DFA dipahami sebagai sebuah mesinNFA dipahami sebagai beberapa mesin kecil yang melakukan komputasi di waktu bersamaan
DFA untuk state selanjutnya bisa ditetapkan dengan jelasNFA untuk state selanjutnya mempunyai banyak kemungkinan
DFA lebih sulit dibuatNFA lebih mudah dibuat
Waktu yang dibutuhkan untuk mengeksekusi string input lebih sedikitWaktu yang dibutuhkan untuk mengeksekusi string input lebih banyak
Semua DFA merupakan NFATidak semua NFA adalah DFA
DFA membutuhkan lebih banyak ruang (space)NFA membutuhkan lebih sedikit ruang (space)

Daftar Artikel Tentang Teori Komputasi

Setelah mengetahui perbedaan DFA dan NFA, berikut merupakan daftar bacaan lengkap terkait Teori Komputasi (Theory of Computation).

Sehingga, pemahaman lebih lanjut mengenai Teori Komputasi bisa lebih dalam dan mudah untuk menerapkannya dalam kehidupan sehari-hari, sebagai salah satu cabang disiplin ilmu artificial intelligence (AI).

Leave a Reply

Your email address will not be published. Required fields are marked *