1501167380 – Angela Muliawan

RE : (ba|bb)*(a|b)*b

Ubah RE sampai DFA minimization, untuk mengubah RE menjadi DFA ada 2 cara yaitu menggunakan tree dan menggunakan cara NFA epsilon.

Cara I

1. Pertama-tama kita membuat tree dari RE, dan memberikan node akhir dengan angka urut. Lalu kita menentukan Firstpost dan Lastpost dari setiap node, untuk nantinya menentukan start state. Hasil dari proses diatas dapat dilihat pada Gambar1 dibawah ini. So yang dihasilkan adalah {1,3,5,6,7}.

Gambar 1

            Dalam menentukan followpos, ada beberapa ketentuan:

a. Node akhir memiliki nilai false (not nullable) dan nilai dari first dan lastpost nya adalah sesuai dengan nomor urutnya.

b. untuk tanda ( | ) firspostnya adalah gabungan dari node kedua anaknya. Nilai true atau falsenya ditentukan dari kedua anaknya, jika keduanya true maka true, jika salah satu false maka false. (and relationship).

c. untuk tanda (*)  nilainya adalah nullable maka true, lalu firstpost nya adalah firstpos dari children 1 (kiri) dan lastpostnya dari children2(kanan).

d. untuk tanda (.)

– untuk firstpost, jika children1 (kiri) bernilai nullable(true) maka nilainya adalah gabungan dari firstpost c1(kiri) dan c2(kanan). Jika c1 tidak bernilai true maka firstpostnya adalah c1.

– untuk lastpost, jika children2 (kanan) bernilai nullable(true) maka nilainya adalah gabungan dari lastpost c1(kiri) dan c2(kanan). Jika c2 tidak bernilai true maka lastpostnya adalah c2.

e. untuk tanda (⁺)  nilainya adalah not nullable maka false, lalu firstpost nya adalah firstpos dari children 1 (kiri) dan lastpostnya dari children2(kanan).

2. Selanjutnya kita mencari Followpost untuk menemukan pergerakan/perpindahan dari satu input keinput lainnya. Proses tersebut dapat dilihat pada Gambar 2. Followpost adalah node mana yang mungkin dilalui saat kita ada di node tertentu.

Gambar 2

3. Langkah berikutnya yaitu mencari perpindahan state beserta inputnya, membutuhkan state awal {S₀} yang telah didapat dari langkah 1, yaitu first post dari induk tree. Proses ini dimulai dari state awal{S₀}, dan di setiap state kita cari pergerakan dari state tersebut bila diberikan input yang ada (pada soal ini input nya{a,b}), lalu kita hubungkan dengan Followpost dari langkah 2 (Gambar 2). Bila hasil penelusuran tidak sama dengan state yang telah ada maka dibuat state baru dan dicari lagi dengan proses diatas. Dan bila di state tersebut terdapat angka Lastpost {8} di Gambar 1 maka state tersebut dijadikan finish state (*). Hasil proses ini dapat dilihat pada Gambar 3.

Contoh pengerjaan:

{So} berisi {1,3,5,6,7}. Untuk input a, cari di antara nomor 1,3,5,6,7 yang mengandung a, yaitu nomor 5. Maka kita tuliskan So input a adalah followpos dari 5 yaitu {5,6,7} dan seterusnya.

 Gambar 3

Dan dari Gambar 3 kita dapat menggambarkan setiap state lalu menghubungkan setiap state sesuai dengan hasil dari input yang diberikan. Hasilnya dapat dilihat pada Gambar 4.

Gambar 4

Cara II –NFA Epsilon

1. Gambarkan NFA Epsilon dari RE.
2. Data node dan closure dari setiap input. Mulai dari mencari So. So didapat dari e-closure node yang paling pertama yaitu node 0. Cek node 0 jika diinput epsilon akan ke node mana saja. Node-node tersebut menjadi S_1. Selanjutnya cek node S1 dan seterusnya, bila diberi input a atau input b, maka node hasil inputan a atau b tersebut akan mengarah ke node apa saja bila diberi input epsilon.
3. Hasil DFA nya. Hasil DFA dari cara tree maupun NFA epsilon akan sama.

DFA Minimization

Setelah kita menemukan DFA seperti pada Gambar 4 maka kita juga dapat menentukan DFA Minimazion. DFA Minimization dapat ditemukan dengan cara kita memisahkan antara final state dan yang bukan final state dan kita beri pengelompokan tersebut dengan nilai index (1,2) seperti yang dapat kita lihat pada Gambar 5. Dan kemudian kita telusuri kembali setiap state tersebut, contoh kita mulai dari state S₀lalu kita beri input a, kita lihat pada Gambar4 kemana S₀ akan pindah bila diberi input tersebut. Disini kita lihat input a akan membuat perpindahan ke state S₁ dan kita lihat lagi pada Gambar5, berada diindex manakah S₁, dan S₁ terdapat diindex 1, maka kita berikan tanda index di sebelah kiri atas (¹S₁), lalu kita input S₀ dengan b, kemanakah dia akan berpindah dan hasil perpindahan tersebut ada diindex berapa dan kita berikan tanda index lagi (²S₂). Dan proses diteruskan hingga semua state telah ditelusuri.

Gambar 5

Lalu setelah kita mencari hasil perpindahannya kita kelompokan lagi setiap state yang akan menuju state dan index yang sama dan berikan setiap state index baru. Gambar dapat dilihat pada bagian bawah. State yang memiliki index yang sama nanti nya akan dijadikan 1 state (Gambar 6).

Lalu setelah kita menemukan state mana yang dijadikan index yang sama maka langkah selanjutnya adalah kita menggambarkan state yang ada diman state dengan index yang sama dijadikan kedalam satu node. Proses tersebut dapat dilihat pada Gambar 6.

Gambar 6

www.binus.ac.id