Finite State Automata dan contoh soal

Finite state automata adalah mesin abstrak berupa sistem model matematika dengan masukan dan keluaran diskrit yang dapat mengenali bahasa paling sederhana (bahasa reguler) dan dapat diimplementasikan secara nyata.

Finite State Automata (FSA) adalah model matematika yang dapat menerima input dan mengeluarkan output yang memiliki state yang berhingga banyaknya dan dapat berpindah dari satu state ke state lainnya berdasarkan input dan fungsi transisi. Finite state automata tidak memiliki tempat penyimpanan/memory, hanya bisa mengingat state terkini.

Finite State Automata dinyatakan oleh pasangan 5 tuple, yaitu:
M=(Q , Σ , δ , S , F )
Q = himpunan state
Σ = himpunan simbol input
δ = fungsi transisi δ : Q × Σ
S = state awal / initial state , S ∈ Q
F = state akhir, F ⊆ Q

Karakteristik Finite Automata
1.Setiap Finite Automata memiliki keadaan dan transisi yang terbatas.
2.Transisi dari satu keadaan ke keadaan lainnya dapat bersifat deterministik atau non-deterministik.
3.Setiap Finite Automata selalu memiliki keadaan awal.
4.Finite Automata dapat memiliki lebih dari satu keadaan akhir.
jika setelah pemrosesan seluruh string, keadaan akhir dicapai, artinya otomata menerima string tersebut.

Setiap FSA memiliki:
1.Himpunan berhingga (finite) status (state)
•Satu buah status sebagai status awal (initial state), biasa dinyatakan q0.
•Beberapa buah status sebagai status akhir (final state).
2.Himpunan berhingga simbol masukan
3.Fungsi transisi
Menentukan status berikutnya dari setiap pasang status dan sebuah simbol masukan.

Cara Kerja Finite State Automata
Finite State Automata bekerja dengan cara mesin membaca memori masukan berupa tape yaitu 1 karakter tiap saat (dari kiri ke kanan) menggunakan head baca yang dikendalikan oleh kotak kendali state berhingga dimana pada mesin terdapat sejumlah state berhingga.

Finite Automata selalu dalam kondisi yang disebut state awal (initial state) pada saat Finite Automata mulai membaca tape. Perubahan state terjadi pada mesin ketika sebuah karakter berikutnya dibaca. Ketika head telah sampai pada akhir tape dan kondisi yang ditemui adalah state akhir, maka string yang terdapat pada tape dikatakan diterima Finite Automata (String-string merupakan milik bahasa bila diterima Finite Automata bahasa tersebut).

Finite State Diagram (FSD)
Finite State Automata dapat dimodelkan dengan Finite State Diagram (FSD) dapat juga disebut State Transition Diagram. Sistem transisi adalah sistem yang tingkah lakunya disajikan dalam bentuk keadaan-keadaan (states). Sistem tersebut dapat bergerak dari state yang satu ke state lainnya sesuai dengan input yang diberikan padanya.
Fungsi Transisi (d) adalah representasi matematis atas transisi keadaan.
S = himpunan alfabet.
Q = himpunan keadaan-keadaan.
d = Q x S à Q

Finite State Diagram terdiri dari:
1.Lingkaran menyatakan state
Lingkaran diberi label sesuai dengan nama state tersebut. Adapun pembagian lingkaran adalah:
•Lingkaran bergaris tunggal berarti state sementara
•Lingkaran bergaris ganda berarti state akhir
2.Anak Panah menyatakan transisi yang terjadi.
Label di anak panah menyatakan simbol yang membuat transisi dari 1 state ke state lain. 1 anak panah diberi
label start untuk menyatakan awal mula transisi dilakukan.

Contoh FSA :

1.   Mesin M = {q, ∑, d ,S,F}

Dimana :
Q = {q0, q1, q2}
∑ = {X,Y}
S=  q0
F = q1

dengan fungsi transisi di atas diberikan dalam bentuk table di bawah ini:

Jadi dari table transisi di atas kita bisa membuat Digram State seperti dibawah ini  

Jika M diberi input xxxyyxy, dengan state awal (q₀, xxxyyxy), maka :

(Q0,xxxyyxy)  ├M (Q0,xxyyxy)
                        ├M (Q0,xyyxy)
                        ├M (Q0,yyxy)
                        ├M (Q1,yxy)
                        ├M (Q0,xy)
                        ├M (Q0,y)
                        ├M (Q1,e)
Karena (Q0,xxxyyxy) ├*M (Q1,e), jadi xxxyyxy diterima oleh M

2.   Mesin M= {q, ∑, d,S,F} diberi  input 101010 dan 110011 serta mempunyai tabel transisi seperti gambar berikut! maka :

Dimana DFA nya

Q = {q0, q1, q2}
∑ = {0,1}
S=  q0
F = q1 

dengan fungsi transisi diatas diberikan dalam bentuk table di bawah ini:

Jadi dari table transisi di atas kita bisa membuat Digram State seperti dibawah ini 

 
Jika M diberi input 101010, dengan state awal (q₀, 101010), maka :

      (q0,101010)  ├M (q1,01010)
                             ├M (q2,1010)
                             ├M (q2,010)
                             ├M (q1,10)
                             ├M (q0,1)
                             ├M (q1,e)
Karena (q0, 101010) ├*M (q1,e), jadi 101010 diterima oleh M


Jika M diberi input 110011, dengan state awal (q₀, 110011), maka :

   (q0,110011)    ├M (q1,10011)
                           ├M (q0,0011)
                           ├M (q0,011)
                           ├M (q0,11)
                           ├M (q1,1)
                           ├M (q0,e)
Karena (q0, 110011) ├*M (q1,e), jadi 110011 tidak diterima oleh M


Sebuah FSA dibentuk dari lingkaran yang menyatakan state:
• Label pada lingkaran adalah nama state
• Busur menyatakan transisi/ perpindahan
• Label pada busur yaitu symbol input
• Lingkaran yang didahului sebuah busur tanpa label menyatakan state awal
• Lingkaranb ganda menyatakan state akhir/ final.
Jadi sebuah mesin otomata dapat dinyatakan dalam diagram transisi, fungsi transisi dan tabel transisi.

Alphabet dan Konkatenasi pada teori bahasa otomata

1.      ALPHABET

• Sebuah alphabet adalah himpunan berhingga dan tak kosong dari simbol.  Alphabet disimbolkan oleh ∑. 
• Contoh:

•              ∑ = {0, 1} alphabet biner

•           ∑ = {a, b,..., z}, himpunan semua huruf kecil.

•            Himpunan semua karakter ASCII.

String

• Sebuah string (atau word) adalah deretan simbol berhingga yang dipilih dari alphabet. 
• Contoh : 011011 dan 1111 adalah string dari alphabet biner ∑ = {0, 1}. 
• String kosong adalah string dimana tidak ada kemunculan simbol.
• String tersebut dinotasikan oleh e.
• Panjang dari string adalah banyaknya posisi untuk simbol dalam string. 
• Contoh, 01101 memiliki panjang 5. 
• Umumnya panjang dari string adalah banyaknya simbol dalam string.
• Pernyataan tersebut tidak sepenuhnya benar, sebagai contoh terdapat 2 simbol dalam string 01101 yaitu 0 dan 1, tetapi terdapat 5 posisi untuk simbol, dan panjangnya adalah 5.
• Notasi standar untuk panjang string w adalah |w|.  Contoh: |011| = 3 dan |e| = 0.
• x adalah sebuah substring dari string lain y jika ada string w dan z, keduanya dapat berupa string kosong, sedemikian sehingga y = wxz. 
• Sebagai contoh, car adalah substring dari carry, car, vicar.

Pangkat dari Alphabet

•   Jika  adalah alphabet, dapat dinyatakan himpunan dari semua string dengan panjang tertentu dari alphabet tersebut dengan menggunakan notasi eksponensial. 

•   Kita mendefinisikan ∑^k sebagai himpunan dari string dengan panjang k, setiap string tersebut memiliki simbol dalam ∑.

• Perhatikan bahwa ∑⁰  = {e}, untuk alphabet apapun. 
• Bahwa e adalah string yang memiliki panjang 0.  Jika ∑ = {a, b, c} maka

∑¹  = {a,b,c }

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

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

2.      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

• Sehingga, string yang satu dapat digabungkan dengan string lainnya:

• Jika x , y dan z  merupakan dua buah string, maka x.y,z diartikan sebagai gabungan dari x y dan z, hasilnya, string yang baru terbentuk dengan menulis x diikuti dengan menuliskan y diikuti dengan menuliskan z .

Contoh:

x = aku y= belajar dan z = pusing

Maka

•   x . y= aku belajar

•  (x . y ).z)=aku belajar pusing

•   (y.z).x= belajar pusing aku     

Bagaimana Proses Pencarian Pada Google

Sebenarnya apa yang terjadi ketika kita mengetikkan kata / kalimat di mesin pencari google? Bagaimana situs tersebut bekerja? Bagaimana Google memberikan data yang cukup akurat di halaman hasil pencariannya?

 Pertanyaan-pertanyaan tersebut kadang terlintas di hati dan fikiran kita. Bagaimana bisa segala informasi yang sangat berlimpah di dunia maya ini dapat di kelompokkan. Sebagai catatan ada lebih dari 100 Petabytes = 100.000.000 Gigabytes data yang tersimpan di indeks Google.

Nah bagaimana Google bisa memilah dan memilih data yang sudah begitu banyak sehingga menampilkan data yang dibutuhkan oleh pengguna saja?

Setidaknya ada 4 langkah sederhana (sederhana bagi kita tetapi bagi google ini adalah langkah yang sangat rumit) dimulai dari kita mengunjungi situs Google dan mulai mengetikkan huruf per huruf kata yang akan kita cari.

Langkah-langkah tersebut adalah :

1. Perayapan & Pengindeksan

Perjalanan kueri dimulai sebelum Anda mengetik penelusuran, dengan perayapan dan pengindeksan web dari triliunan dokumen.

Google mengolah data yang 100 Petabytes tadi agar sesuai dengan kata yang kalian cari yaitu dengan cara merayapi semua situs web dan blog yang ada du dunia ini, bagi blogger tentunya sudah tidak terlalu asing dengan kata "GoogleBot" atau sering disebut robot perayap google / google spider.

Ada 3 hal yang dilakukan oleh Google yang berkaitan hal ini, yaitu :

1. Mencari Informasi Dengan Perayapan
   "GoogleBot" adalah progam khusus yang dirancang Google untuk jalan-jalan menelusuri situs web / blog guna mencari informasi yang akan ditampilkan kepada pencari informasi. Perayap ini akan memberikan perhatian yang berlebih mengenai situs-situs baru, perubahan pada situs yang sudah ada, tautan mati yang ada di website.
2. Mengatur Informasi Dengan Pengindeksan
   Google diibaratkan adalah sebuah perputakaan besar dengan dukungan dari milyaran informasi yang ada di dalamnya. Nah perayap google ibarat seorang pustakawan yang mengindeks dan mengingat dimana letak informasi-informasi itu berada. Jadi ketika kalian menginginkan suatu informasi mengenai "PPC" kalian tidak serta merta diberikan informasi mengenai "apa itu ppc" tetapi kalian juga mungkin akan diberitahu "masa depan ppc indonesia" dan "Belajar ppc bersama adsensecamp", semua yang berkaitan dengan ppc akan ditampilkan oleh Google. Hal ini selain akan memberikan pilihan yang lebih luas kepada penguna juga akan memberika informasi yang baru dan memang harus diketahui oleh pengguna google.
3. "robot.txt" atau pengikdeksan khusus
   Ada kalanya ketika kita membuat artikel atau informasi tertentu di dunia maya ini, kita tidak ingin informasi tersebut dilihat oleh sembarang orang. Karena informasi tersebut bersifat khusus (contoh hanya untuk diri sendiri atau hanya untuk anggota dari situs tersebut saja), kita sebagai pemilik website dapat mengatur mana informasi yang boleh ditampilkan oleh google dan mana yang tidak boleh ditampilkan, hal ini dapat diatur menggunakan file robot.txt

2. Algoritme

Anda mau jawaban, bukan triliunan laman web. Algoritme adalah program komputer yang mencari petunjuk untuk memberikan tepat apa yang Anda inginkan. Algoritme Google hari ini mengandalkan lebih dari 200 sinyal unik atau “petunjuk” yang membuatnya dapat menebak apa yang mungkin benar-benar Anda cari. Sinyal ini meliputi hal-hal seperti istilah di situs web, kesegaran konten, wilayah Anda, dan PageRank.

Sama seperti contoh PPC diatas, meski kita mencari kata ppc bukan berarti kita hanya mencari kata ppc saja mungkin kita juga mencari hal-hal yang berkaitan dengan ppc. Google senantiasa mengupdate algorithma mereka sehingga dapat mengesampingkan informasi-informasi yang kurang bermanfaat dan hanya menampilkan informasi yang akan memberikan manfaat nyata bagi pencarinya. Secara spesifik Google mengatakan bahwa hasil pencarian yang sesuai dengan situs web (semakin terpercaya situs web maka akan semakin sering di pajang di rak pertama oleh google), kesegaran konten (apabila kalian mengetikkan kata "berita bola terbaru" maka google secara spesifik akan mencari informasi mengenai berita bola dengan tanggal update tak jauh dari tanggal kalian mencari kata tersebut), Wilayah (contoh ketika kalian mencari informasi mengenai "pabrik kereta mini" kalian tentu tidak mencari pabrik kereta mini yang berada di luar negeri bukan? kalian tentu mencari yang dalam negeri dahulu, nah Google juga mengetahui tentang hal itu karenanya google akan menampilkan situs web yang masih masuk dalam regional kalian terlebih dahulu), PageRank (semakin tinggi pagerank suatu website maka akan ditempatkan terdahulu oleh google, meski pada beberapa kasus hal ini tidak berat).

3. Memerangi Spam

Setiap hari, jutaan laman spam yang tidak berguna dibuat. Kami memerangi spam melalui kombinasi algoritme komputer dan tinjauan manual.  

Ada banyak cara yang dilakukan oleh para blogger nakal untuk membuat konten yang berisi spam. Beberapa jenis spam yang masuk kedalam indikasi google adalah :

1. Pengalihan licik dan atau penyelubungan
   Yang masuk kategori ini adalah situs yang menampilkan halaman yang berbeda dengan apa yang kita pilih.
2. Spam murni
   Situs yang melakukan copy paste atikel milik situs lain, atau memberikan informasi yang murni hanya membohongi pengguna dimasukkan kedalam kategori spam murni.
3. Tautan tidak wajar dari situs
   Hampir sama dengan point 1, tapi terkadang tautan yang diberikan berupa iklan dari situs lain.
4. Situs yang diretas
   Situs yang telah diretas oleh orang lain akan menyajikan informasi yang tidak sesuai dengan informasi aslinya. Nah google secara spesifik akan menyingkirkan situs-situs yang diretas ini dari halaman pencariannya agar pesan-pesan dari peretas situs tersebut tidak dibaca oleh orang banyak.
5. Hosting gratis yang menyajikan spam
   Sebagian besar hosting gratis akan memberikan spam berupa iklan kepada situs-situs yang mereka kelola, hal ini yang dicoba untuk disingkirkan oleh google.
6. Teks tersembunyi dan penjejalan kata kunci
   Teknik yang sering juga disebut sebagai Black Hat SEO ini sangat amat teramat dibenci oleh Google. adi jagan pernah mencoba teknik ini agar situs kalian tidak dikenai sanksi oleh goolge berupa penghapusan situs kalian dari daftar pencarian mereka.
7. Konten tanpa nilai tambah
   Kalian tentu mencari informasi yang bermutu bukan? Oleh karena itu google akan menyajikan konten-konten yang bermutu saja, sebuah konten tanpa nilai tambah yang berarti akan ditampilkan belakangan oleh sanga raksasa pencari ini.

Nah tugas dari GoogleBot juga mencari konten-konten spam ini dan sesegera mungkin mengambil tindakan agar informasi yang didaptkan oleh pengguna adalah informasi yang berguna. GoogleBot akan memberikan tangkapan langsung atau screenshot tentang konten spam, ketika mereka (perayap .pen) menemukan konten spam hal yang pertama dilakukan adalah menyingkirkan konten tersebut dari halaman pencarian atau apabila kasusnya sudah sangat fatal Google akan menghapus konten tersebut secara permanen dari hasil pencarian mereka. Sebelum google menghapus konten dari sebuah situs google akan memberitahu kepada pemilik situs tersebut tentang kesalahannya dan menerima masukan tentang penangguhan penghapusan tersebut.

4. Kebijakan Pencarian Google

Google sangat memperhatikan informasi yang dibaca dan ditemukan di halaman hasil pencarian google. Google akan menyajikan informasi yang benar-benar dibutuhkan pengguna dengan berbagai pendekatan tertentu.

Dalam hal ini Google memiliki kebijakan tersendiri berupa akses informasi yang sesuai,telusur aman, konten dewasa, pencurinan identitas, spam, kebijakan sesuai hukum yang berlaku, dll.

Demikianlah 4 langkah sederhana yang dilakukan oleh Google ketika kalian ingin mencari tentang segala macam informasi di dunia ini. Dengan mengetahui cara-cara google bekerja kita tentu dapat melakukan teknik seo terbaik agar blog / website yang kita kelola semakin bersahabat dengan Google. Ada istilah tuntutlah ilmu pada gurunya, kalau mau mencari ilmu tentang search engine optimizations / SEO bertanya / bergurulah pada search engine itu sendiri.