Konversi NFA (Non-Deterministic Finite Automata) ke DFA (Deterministic Finite Automata)

Pada tutorial kali ini, aku akan coba jelaskan gimana cara konversi dari NFA ke DFA. Kita tau, bahwa NFA bisa transisi ke lebih dari 1 state jika diberi input yang sama. Berbeda dengan DFA, yang hanya bisa transisi ke 1 state jika diberi input tersebut. Gimanasih langkah-langkahnya?

Langkah-langkah Konversi NFA-DFA

Buat tabel transisi NFA

Jika diberi transition diagram, ubah ke tabel transisi.

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

Sudah pusing? Hahahaha, skuy langsung ke contoh soal!

Soal NFA 1

Jawabannya di bawah ini

Soal NFA 2

Jawabannya di bawah ini

Sekian tutorial konversi dari NFA ke DFA, apabila ada pertanyaan langsung komentar di bawah ya! Terimakasih!