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).
DFA adalah Finite-state Machine atau mesin keadaan terbatas yang menerima atau menolak string dari simbol dan hanya menghasilkan perhitungan unik dari otomata untuk setiap string yang di masukan.
Langkah-langkah Konversi NFA-DFA
Buat tabel transisi NFA
Jika diberi transition diagram, ubah ke tabel transisi.
Buat tabel transisi DFA
Buat tabel transisi DFA
1. Salin kondisi state awal dari NFA ke kondisi state awal DFA.
2. Jika ditemukan state baru saat transisi, masukkan state tersebut ke state di DFA.
3. Apabila state baru tersebut merupakan gabungan dari beberapa state, maka hasil transisinya adalah gabungan dari transisi beberapa state. Contohnya transisi state [q0, q1] ke 0, adalah transisi state q0 ke 0 digabung transisi state q1 ke 0.
4. Apabila state memiliki final state maka state tersebut adalah final state
5. Ulangi langkah 2-4 sampai semua state terdaftar
No comments:
Post a Comment