Ekuivalensi NFA ke DFA

Selamat datang di blog saya, perkenalkan saya Rina Setiyaningsih dengan NIM 202131022 , Mahasiswi Informatika dan berkuliah di Institut Teknologi PLN Jakarta.

Disini saya akan membahas ulang materi yang sudah disampaikan Bu DINE TIARA KUSUMA ,S.T., M.Kom. pada pertemuan di hari Rabu, 7 Juni 2023, materi yang disampaikan adalah pembahasan tentang teori Ekuivalensi NFA ke DFA.

 

Pembahasan Awal

• FSA terdiri atas  : DFA dan NFA
• Perbedaan antar keduanya terlihat dari tabel transisi dan diagram. 

• ·      Berikut untuk DFA

• ·      Berikut untuk NFA

• Kesimpulan perbedaannya adalah : 

NFA adalah istilah yang digunakan dalam teori automata. NFA adalah singkatan dari Finite Automata dan mewakili diagram transisi di mana beberapa jalur dapat diambil untuk berpindah dari satu keadaan ke keadaan lainnya. DFA adalah singkatan dari Deterministic Finite Automata. Ini juga menyajikan diagram transisi di mana hanya satu jalur yang dapat diambil untuk berpindah dari satu keadaan ke keadaan lainnya.

 

Ekuivalensi NFA ke DFA

 

 

• Ekuivalensi Non-Deterministic Finite Automata ke Deterministic Finite Automata
• Dari sebuah mesin Non-Deterministic Finite Automata dapat dibuat mesin Deterministic Finite Automata-nya yang ekuivalen (bersesuaian). Ekuivalen disini artinyaa mampu menerima bahasa yang sama

Sebagai contoh, akan dibuat Deterministic Finite Automata dari Non-Deterministic Finite Automata berikut :

 

δ  = {q0 , q1}

Ʃ = {0 , 1}

s =  q0

f =  q1

 

Langkah-langkah

 

1.     Buat table transisi dari diagram transisi tersebut :

2.         Buat diagram transisi untuk finite state automata dari tabel transisi diatas

Catatan : perhatikan bahwa disini pada gambar setiap state kita tuliskan sebagai himpunan state

3.    Tabel Transisi Ekuivalensi NFA ke DFA

Menambahkan state baru yaitu {q_{0 ,} q₁} dan empty , dikarenakan terciptanya state baru maka nanti saat didalam diagram terdapat perolehan input 1 atau 0 juga

4.     Diagram transisi ekuivalensi NFA ke DFA

Berikut diatas ini merupakan penjelasan Ekivalensi Non-Deterministic Automata (NFA)  ke Deterministic Finite Automata (DFA).

Pembahasaan materi pada 7 Juni 2023 . Sekian yang bisa saya sampaikan, Mohon maaf bila ada salah pengetikan.

Terimakasih, Sampai bertemu di penyampaian materi berikutnya👐😊

Wassalamualaikum Warrahmatullahi Wabarrakatuh