Mesin Abstrak FSA (Finite State Automata) - JFLAP 7.0

Selamat Malam,

Di kesempatan kali ini saya bermaksut untuk menjelaskan sedikit tentang FSA (Finite State Automata). Apa itu FSA? Finite State Automata adalah sebuah mesin abstrak berupa sistem matematika dengan masukan dan keluaran diskrit yang dapat mengenali bahasa paling sederhana (bahasa reguler) dan dapat diimplementasikan secara nyata.

Finite State Automata dinyatakan oleh pasangan 5 tuple, yaitu:

M=(Q , Σ , δ , S , F ) 

Q = himpunan state

Σ = himpunan simbol input
δ = fungsi transisi
S = state awal / initial state
F = state akhir

FSA sendiri memiliki karakteristik, yaitu:

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.

Bagaimana cara kerjanya? 

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

Contoh

Pada gambar contoh diatas, tuple nya sebagai berikut:

M=(Q , Σ , δ , S , F ) 

Q = {q0,q1,q2,q3,q4,q5}

Σ = {0.1}

S = q0

F = q5

δ = tabel ->

δ tabel

Kemudian kita uji dengan aplikasi JFLAP dan hasilnya sbegai berikut. Temen temen bisa download aplikasi JFLAP ini disini gratis.

Dapat dilihat pada result disebalah kanannya terdapat inputan mesin

1001 = Accept

0001 = Accept

1010 = Reject

0110 = Reject

disini kita bahas kenapa Accept dan Reject. kita lihat di inputan 1001 

accept state

Berikut kenapa ada accept artinya inputan tersebut berhasil sampai ke Final State, dan kenapa reject karena inputan tersebut tidak sampai di Final State.

reject state

Nah. Tadi itu seputar FSA nya, selanjutnya kita akan bahas Grammar pada Automata dan kita olah dari FSA yg sudah ada atau boleh membuat baru lagi. Pada contoh yang akan saya berikan adalah membuat baru. Karena bisa saja convert yang sudah ada dari JFLAP nya.

Grammar

Grammar G didefinisikan sebagai pasangan 4 tuple, G = V , T , P , S

V = simbol variabel 

T = simbol terminal
P = Kumpulan aturan produksi
S = Simbol awal.

Langsung ke contoh.

G = V , S , T , P , S

V = S , A , B , C , D , E

T = 0,1

S = q0

F = q1

P = { S= 0C | 1B , B = 0B | 1D , C = 0A | 1B , D = 0E | 1D , E =  1D | 1B }

Sekian, semoga mengerti hehe.

Jika ada yang kurang dimengerti silahkan komen dibawah ya. Kritik dan Saran sangat terbuka :)

Terima Kasih

Nama : Henry Taswin

NIM : 161021450263

Kelas : 05TPLE004