Teori Bahasa Otomata

Algoritma searching BFS dan DFS

Membahas dua buah algoritma searching yaitu Breadth-First Search (BFS) dan Depth-First Search (DFS).

Nah sekarang bagaimana logika algoritma tersebut? langsung aja...

Untuk menyederhanakannya sebaiknya kita gunakan contoh tree berikut yah...

 

Misalkan kita ingin mencari apakah ada path dari A menuju G. Node - node mana saja yang akan kita lewati? Kita akan menggunakan sebuah list yang berisi node-node yang dilewati oleh algoritma searching tersebut.

Pada saat awal, list akan berisi node awal yaitu A, {A}. Selanjutnya dari node A akan menuju node B dan C, jangan lupa menghapus node A dari list karena telah digantikan oleh node B dan C, {B, C}. Selanjutnya adalah menghapus B dari list dan menggantinya dengan node D dan E, {C, D, E}. Ingat bahwa breadth-first memperlakukan node yang memiliki depth terendah lebih dulu sehingga D dan E diletakkan setelah C karena D dan E memiliki depth 3 sedangkan C memiliki depth 2 (sama dengan B). Selanjutnya kita menghapus C dan menggantinya dengan F dan G sehingga list akan berisi {D, E, F, G}. Akhirnya node G ditemukan juga dan membuat searching berakhir dengan sukses.

Bagaimana jika menggunakan depth-first search? Pertama kali list berisi node A, {A}. Kemudian A dihapus dari list dan diganti dengan B dan C, {B, C}. Selanjutnya B diganti dengan D dan E dengan meletakkan keduanya di depan (kebalikan breadth-first), {D, E, C}. Karena D dan E berupa leaf maka keduanya bisa dhapus dari list sehingga tersisa C, {C}. Kemudian node C diganti dengan F dan G, {F, G}. Node G ditemukan dan proses searching berakhir dengan sukses.

Jika digambarkan, maka urut-urutan node mana yang diproses terlebih dahulu pada breadth-first search akan terlihat seperti berikut






Sedangkan jika menggunakan depth-first search akan terlihat urut-urutan node yang diproses seperti berikut

 
 Sekian dulu dari saya... tentunya saya cantumkan sumber yang saya peroleh ...

(http://rochmatsantoso.blogspot.com/2009/04/breadth-first-depth-first-search.html)

Selanjutnya.....

Pangkat Alfabet

Jika S = {0, 1}, maka

•      S merupakan alfabet

•      simbol 0 dan simbol 1 merupakan anggotanya.

•      S¹ merupakan himpunan string;

•      masing-masing anggotanya merupakan string (dengan panjang masing-masing 1)

Yuk  kita Langsung aja kerjakan soal dibawah ini...

Jika S = {a, b,c}, maka

•      S²= {aa,bb,cc,ab,ba,bc,cb, ac,ca}

•      S³= {aaa,aab,aba,baa,aac,aca,caa,bbb,bba,bab,abb,bbc,bcb,cbb, ccc,cca,cac,acc,ccb,cbc,bcc, abc,acb,bca,bac,cba,cab}

 



The Next.....

Konkatenasi

Didefinisikan suatu operasi biner, dinamakan konkatenasi (gabungan), dalam S* , sbb:

•      Jika a₁a₂a₃…a_n dan b₁b₂…b_m berada dalam S*, maka

a₁a₂a₃...a_n.b₁b₂…b_m = a₁a₂a₃…a_nb₁b₂…b_m

Dengan demikian......

Langsung aja kita kerjakan soal dibawah ini yah...

S merupakan himpunan huruf kecil

      Jika S = {a,b,c ,.....z}

dimana x = aku, y = belajar, dan z = pusing

maka

untuk x . y = aku . belajar = akubelajar

            kemudian (x . y ) . z = aku . belajar . pusing = akubelajarpusing

            selanjutnya ( y . z ). x = belajar . pusing . aku = belajarpusingaku 

Sampai jumpa pada postingan berikutnya... 

JESUS Bless You and Me