Artikel kali ini merupakan lanjutan pembahasan dari series artikel Teori Bahasa dan Automata, dimana sebelumnya kita telah membahas mengenai Hirarki Chomsky dan Aturan Produksi.
Apa itu FSA?
- FSA adalah mesin abstrak berupa sistem model matematika dengan masukan dan keluaran diskrit yang dapat mengenali bahasa paling sederhana
- mekanisme kerja FSA dapat diterapkan pada analisis leksikal, text editor, protocol dan komunikasi jaringan
contoh analisis leksikal:
- analisis leksikan adalah salah satu bagian dari proses penerjemahan
- code yang dituliskan akan dianalisis seperti yang mana variabel, operator, keyword
Arti bentuk symbol pada graf transisi FSA
Keterangan gambar:
- Initial state ditandai dengan busur tanpa asal
- Lingkaran menyatakan state
- Label pada lingkaran adalah nama state, yaitu EVEN dan ODD
- Busur adalah transisi / arah perpindahan state
- Label pada busur adalah simbol input, yaitu 0 dan 1
- Lingkaran ganda menyatakan final state, yaitu ODD
Pernyataan Final State Automata secara Formal
FSA dapat dinyatakan dalam 5 tupel atau M=(Q, Σ, δ, q0, F) dimana:
- Q adalah Himpunan state atau kedudukan
- Σ (dibaca: sigma) adalah Himpunan symbol input / masukan / abjad
- Jika pada contoh sebelumnya, terdapat input / simbol yaitu 0 dan 1
- δ (dibaca: delta) adalah Fungsi transisi
- q0 (atau bisa juga S) adalah State awal q0. dimana q0 Q
- F adalah Himpunan State akhir (final) F ⊆ Q
Catatan:
- Jumlah state akhir bisa lebih dari satu
Contoh:
- Q = {ODD, EVEN}
- Σ = {0, 1}
- q0 = EVEN
- F = {ODD}
- δ (Transisi):
- δ(EVEN, 0) = EVEN State EVEN menerima inputan 0 ke EVEN
- δ(EVEN, 1) = ODD
- δ(ODD, 0) = ODD
- δ(ODD, 1) = EVEN
catatan: Final state F = {ODD} berupa himpunan karena final state dapat berjumlah lebih dari satu
Jadi aturan ini menyesuaikan model mesinnya
Contoh ketika mesin digunakan:
- Ketika mendapat input 1101, maka urutan state yang terjadi adalah EVEN1ODD1EVEN0EVEN1ODD
- berakhir dengan state ODD, maka 1011 diterima mesin
- Karena diterima maka dapat diketahui bahwa jumlah bit 1 nya adalah ganjil
Contoh Lain:
- Ketika mendapat input 101, maka urutan state yang terjadi adalah EVEN1ODD0ODD1EVEN
- berakhir dengan state EVEN, maka 101 ditolak mesin
- Karena ditolak maka dapat diketahui nilai bit nya genap
Berdasarkan pendefinisian kemampuan merubah statenya, FSA dikelompokkan kedalam 2 jenis, yaitu:
- Deterministic FSA
- Non Deterministic FSA
Kesimpulan
Apabila kita lihat kembali ilustrasi pada contoh sebelumnya, maka bisa kita simpulkan pada Mesin Automata tersebut bahwa
- jika 1 nya ada genap berarti genap, contoh (0110 -> output Genap)
- jika 1 nya ada ganjil maka hasilnya akan ganjil, contoh (1011 -> output Ganjil)
- Mengapa demikian? karena apabila kita lihat graf nya terdapat simbol 0 dan 1 dimana simbol 0 selalu mengarah ke state itu sendiri. Sedangkan simbol 1 akan menyebabkan pergantian state (transisi)
- Jadi 0 tidak terlalu berpengaruh
Referensi:
Artikel ini merupakan hasil resume dari video PAKKODING (web, youtube).
Video berjudul: #4 Teori Bahasa & Otomata – Finite State Automata
Terima kasih banyak ke pada PAKKODING atas materi yang disampaikan serta cara penyampaiannya yang mudah dipahami.
