Teori Bahasa Outomata

SOAL :

Tugas 1

Bagaimana proses pencarian pada Google :

                   Cara kerja Mesin Pencari Google

Salah satu inovasi utama adalah PageRank, sebuah teknologi yang menentukan "pentingnya" dari sebuah halaman web dengan melihat, apakah terdapat link halaman lain ke halaman web tsb berserta data lainnya? Google menggunakan lebih dari 200 sinyal, termasuk PageRank dan memperbarui algoritma ini setiap minggu. Sebagai contoh, google menawarkan hasil pencarian yang dipersonalisasi berdasarkan riwayat web Anda dan lokasi.

Kelengkapan.

Google diluncurkan pada tahun 1998 hanya dengan 25 juta halaman, saat itu merupakan sebagian kecil dari web. Kini google mempunyai indeks bermiliar-miliar halaman web, dan indeks google adalah sekitar 100 juta gigabyte. Google terus berinvestasi untuk menambah kelengkapan layanan kami. Pada tahun 2007 kami memperkenalkan Universal Search, yang membuat pencarian lebih komprehensif dengan mengintegrasikan gambar, video, berita, buku dan lebih ke hasil pencarian utama kami.

Kesegaran.

Pada masa awal, Googlebots merayapi Web setiap tiga atau empat bulan, yang berarti bahwa informasi yang Anda ditemukan di Google biasanya adalah dari per tanggal. Sekarang google terus merangkak Web memastikan bahwa Anda dapat menemukan berita terbaru, blog dan update status tiap menit atau bahkan detik setelah mereka mem-posting sebuah artikel.

Kecepatan.

Rata-rata waktu respon query kita kira-kira seperempat detik. Sebagai perbandingan, rata-rata berkedip mata adalah satu-sepersepuluh detik. Kecepatan adalah prioritas pencari utama, itulah sebabnya mengapa pada umumnya google tidak mengaktifkan fitur baru jika mereka akan memperlambat layanan google ke bawah. Sebaliknya, insinyur mesin pencari google selalu bekerja tidak hanya pada fitur baru, melainkan juga cara-cara untuk membuat pencarian lebih cepat. Selain smart coding, di belakang google telah mengembangkan sistem komputasi pendistribusian untuk memastikan Anda mendapatkan waktu respon yang cepat. Dengan teknologi seperti autocomplete dan Google Instan , google membantu menemukan istilah pencarian untuk hasil yang Anda cari, bahkan sebelum Anda selesai mengetik.Bagaimana proses pencarian pada Google :

                   Cara kerja Mesin Pencari Google

Salah satu inovasi utama adalah PageRank, sebuah teknologi yang menentukan "pentingnya" dari sebuah halaman web dengan melihat, apakah terdapat link halaman lain ke halaman web tsb berserta data lainnya? Google menggunakan lebih dari 200 sinyal, termasuk PageRank dan memperbarui algoritma ini setiap minggu. Sebagai contoh, google menawarkan hasil pencarian yang dipersonalisasi berdasarkan riwayat web Anda dan lokasi.

Kelengkapan.

Google diluncurkan pada tahun 1998 hanya dengan 25 juta halaman, saat itu merupakan sebagian kecil dari web. Kini google mempunyai indeks bermiliar-miliar halaman web, dan indeks google adalah sekitar 100 juta gigabyte. Google terus berinvestasi untuk menambah kelengkapan layanan kami. Pada tahun 2007 kami memperkenalkan Universal Search, yang membuat pencarian lebih komprehensif dengan mengintegrasikan gambar, video, berita, buku dan lebih ke hasil pencarian utama kami.

Kesegaran.

Pada masa awal, Googlebots merayapi Web setiap tiga atau empat bulan, yang berarti bahwa informasi yang Anda ditemukan di Google biasanya adalah dari per tanggal. Sekarang google terus merangkak Web memastikan bahwa Anda dapat menemukan berita terbaru, blog dan update status tiap menit atau bahkan detik setelah mereka mem-posting sebuah artikel.

Kecepatan.

Rata-rata waktu respon query kita kira-kira seperempat detik. Sebagai perbandingan, rata-rata berkedip mata adalah satu-sepersepuluh detik. Kecepatan adalah prioritas pencari utama, itulah sebabnya mengapa pada umumnya google tidak mengaktifkan fitur baru jika mereka akan memperlambat layanan google ke bawah. Sebaliknya, insinyur mesin pencari google selalu bekerja tidak hanya pada fitur baru, melainkan juga cara-cara untuk membuat pencarian lebih cepat. Selain smart coding, di belakang google telah mengembangkan sistem komputasi pendistribusian untuk memastikan Anda mendapatkan waktu respon yang cepat. Dengan teknologi seperti autocomplete dan Google Instan , google membantu menemukan istilah pencarian untuk hasil yang Anda cari, bahkan sebelum Anda selesai mengetik.

Tugas 2 

1.      Buatlah bahasa minimal 5 buah dengan aturan himpunan string terdiri dari n buah ≤ diikuti oleh n+2      ∑”

2.     

Jawaban :

1.      n=0 diikuti n+2 =1

a.      n =1 diikuti 0111

b.      n =2 diikuti 001111

c.       n =3 diikuti 00011111

d.      n =4 diikuti 0000111111

e.       n =5 diikuti 000001111111

2.  Diketahui :        S = {ﻍ,00,001,111}

       P ={ﻍ 101,111,001,11}

Ditanya : S union P  ??  

Maka S union P ={ﻍ ,00,001,101,11,111}

3.   Lakukan operasi konkatenasi di soal nomor 2 ?

   diketahui :

 S = {ﻍ,00,001,111}

 P ={ﻍ ,101,111,001,11}

Maka S konkatenasi P={00,001,101,11,111,00101,00111,00001,0011,001101,001111,001001,00111,111101,111111,111001,11111}

Tugas 3

DFSA/DFA 

1.)   Buatlah tabel transisinya

2.)   Bacalah input              

                                          a = abbabbaaa

                                          b = bbbabbaa

                                          c = ab

Jawaban :

1.) Tabel Transisi :

                   δ         a            b

        →     q0     q0,q2       q1

        *       q1     q1,q2       q2

                 q2        -           q0,q1

2.) Baca Inputnya :

a. Jika T diberi input abbabbaaa dengan State awal (q0, abbabbaaa), maka :

q0, abbabbaaa   ┣ T (q0, bbabbaaa)

                          ┣ T (q1, babbaaa)

                          ┣ T (q1, abbaaa)

                          ┣ T (q2, bbaaa)

                          ┣ T (q1,baaa)

                          ┣ T (q1,aaa)

                          ┣ T (q1,aa)

                          ┣ T (q1,a)

                          ┣ T (q1,e)

Karena (q0, abbabbaaa) ┣ * T jadi abbabbaaa diterima T

b. Jika T diberi input bbbabbaa dengan State awal(q0, bbbabbaa), maka :

q0, bbbabbaa      ┣ T (q1,bbabbaa)

                           ┣ T (q1,babbaa)

                           ┣ T (q1,abbaa)

                           ┣ T (q2,bbaa)

                           ┣ T (q0,baa)

                           ┣ T(q1,aa)

                           ┣ T(q1,a)

                           ┣ T (q1,e)

Karena (q0,bbbabbaa) ┣ * T jadi bbbabbaa diterima T

c. Jika T diberi input ab dengan State awal (q0,ab), maka :

q0, ab    ┣ T (q0,b)

              ┣ T (q1,e)

Karena (q0,ab) ┣ * T jadi ab diterima T

Tugas 4

 1.)    Soal :

Dari diagram state di atas tentukan :

  a. ABAAAAB

  b. BBBBAAA

  c. BABABAB

Jawaban : 

 a. ABAAAAB

  b. BBBBAAA

  c. BABABAB