Teori Bahasa dan Automata - Minimalisasi DFA

INGAT ! yang bisa diminimalisasi hanya bentuk DFA. Jikalau masih dalam bentuk NFA ubahlah ke bentuk DFA dahulu (DFA Ekivalen)

Contoh: Diketahui DFA

Minimalisasi:
1. Pisahkan Non - Final State dan Final State

   Non - FinalState              FinalState
        1, 3                                   2

2. Masukkan input ke setiap state seperti dibawah, jika ada lebih dari 1 state yang mengarah ke state yang sama jika diberi input yang sama, maka dikatakan indistinguishable.

Non-Final State

 -> State 1 dan 3 dikatakan indistinguishable karena jika diberi input a dan b akan mengarah ke state yang sama

Final State







3. Buat tabel Minimalisasi
Caranya: Buat tabel dengan kolom sesuai jumlah state-1 dan Baris sejumlah state-1. Beri tanda X jika pasangan state tidak sama (distinguishable) dan tanda O bila pasangan state ekivalen (indistinguishable)

4. Buat transition diagramnya
Transition Diagram yang diminimalisasi:

Contoh Latihan soal yang lebih rumit (dari slide, silahkan pelajari sendiri dari penjellasan yang sudah diberikan)