A. PENGERTIAN
FSA (Finite State Automata) merupakan tool yang sangat berguna dalam perancangan lexical analyzer, yaitu bagian dari kompilator yang mengelompokan karakter-karakter ke dalam sebuah token, yang berupa unit terkecil seperti nama, variabel, dan keyword. FSA dipakai untuk penganalisa leksikal dan dipakai juga dalam text editor, pemrosesan teks, dan program file-searchingFSA dapat juga sebagai :
- Model matematika suatu sistem yang menerima input dan output diskrit
- Mesin automata dari bahasa Regular
- Tidak memiliki tempat penyimpanan sehingga kemampuan mengingat terbatas (contoh: elevator/lift)
- Aplikatif - berguna untuk merancang
sistem
nyata. - Aplikasi meliputi : analisis leksikal, text-editor,
protokol komunikasi jaringan (kermit) dan parity checker (pengecek
parity).
FSA atau AH (Automata Hingga)
didefinisikan sebagai pasangan 5 tupel à M = (Q, ∑, δ, S, F).
- Q : himpunan hingga state
- ∑ : himpunan hingga simbol input (alfabet)
- δ : fungsi transisi, menggambarkan transisi state FSA akibat pembacaan simbol input. Fungsi transisi ini biasanya diberikan dalam bentuk tabel.
- S Î Q : state AWAL
- F Í Q : himpunan state AKHIR
Mesin ini memiliki 6 state
(q0,q1,q2,q3,q4,q5). State awal q0, q3 dan q4 adalah state akhir, sedangkan
simbol input adalah (a,d,u)
CONTOH
CONTOH
Contoh : FSA untuk mengecek parity
ganjil
Q ={Gnp, Gjl}
∑ = {0,1}
TABEL TRANSISI
CONTOHGjl Gjl Gnp
Seorang petani dengan seekor serigala, kambing dan seikat rumput berada pada suatu sisi sungai. Tersedia hanya sebuah perahu kecil yang hanya dapat dimuati dengan petani tersebut dengan salah satu serigala, kambing atau rumput. Petani tersebut harus menyeberangkan ketiga bawaannya kesisi lain sungai. Tetapi jika petani meninggalkan serigala dan kambing pada suatu saat, maka kambing akan dimakan serigala. Begitu pula jika kambing ditinggalkan dengan rumput, maka rumput akan dimakan oleh kambing. Mungkinkah ditemukan suatu cara untuk melintasi sungai tanpa menyebabkan kambing atau rumput dimakan.
Seorang petani dengan seekor serigala, kambing dan seikat rumput berada pada suatu sisi sungai. Tersedia hanya sebuah perahu kecil yang hanya dapat dimuati dengan petani tersebut dengan salah satu serigala, kambing atau rumput. Petani tersebut harus menyeberangkan ketiga bawaannya kesisi lain sungai. Tetapi jika petani meninggalkan serigala dan kambing pada suatu saat, maka kambing akan dimakan serigala. Begitu pula jika kambing ditinggalkan dengan rumput, maka rumput akan dimakan oleh kambing. Mungkinkah ditemukan suatu cara untuk melintasi sungai tanpa menyebabkan kambing atau rumput dimakan.
Tidak ada komentar:
Posting Komentar