Finite State Automata

Diposting oleh Yudi Herdiana 21.58

Analisis leksikal lebih mudah diimplementasikan pada Finite State Machine atau Finite State Automata (FSA). FSA mempelajari sehimpunan state (anggota himpunannya terbatas) beserta dengan aturan-aturan perpindahan dari satu state ke state lainnya. Sehimpunan state tersebut menyatakan satu proses dan aturan-aturannya menyatakan kemungkinan-kemungkinan yang terjadi dalam menyelesaikan proses tersebut.

State Diagram dan State Table

Contoh:

Ada mesin penjual permen yang memuat aturan-aturan sebagai berikut:

Harga perman Rp.25.
Mesin dapat dimasuki 3 jenis koin yaitu Rp. 5 (n), Rp. 10 (d), Rp. 25 (q).
$ = tombol untuk mengeluarkan permen.

Kemungkinan=kemungkinan yang terjadi dalam proses digambarkan dalam state diagram sebagai berikut:

Lingkaran menggambarkan state (automation). Ada 7 state yang ditandai dengan nomor 0 sampai dengan 6. Lingkaran tipis menandakan non terminal state (yang harus dilanjutkan) dan lingkaran tebal menandakan terminal state atau disebut acceptance state. Bila proses sampai pada state ini maka mesin akan segera mengeluarkan permen. Tanda panah menunjukkan perubahan dari satu state ke state lainnya, bila diberikan masukan seperti yang ditunjukkan oleh huruf (n = Rp 5, d= Rp 10, q = Rp 25 dan $ = mengeluarkan permen).

Proses dimulai dari state 0. Bila pembeli memasukkan koin Rp 5 (n) maka akan pindah ke state 1. Bila koin Rp 10 (d) yang dimasukkan, pindah ke state 2, dan bila langsung memasuki koin Rp 25, maka langsung ke state 5. Di state 5 pembeli dapat menekan tombol $ maka state dan permen akan keluar dan state kembali ke 0. Pada state 0, karena belum ada koin masuk atau belum cukup sehingga bila ditekan tombol $ maka state tidak akan pindah. Demikian juga untuk state-state lain yang non terminal state.

State 6 adalah state yang menampung kelebihan koin. Bila pembeli memasukkan koin lagi maka koin tersebut tidak diterima (kembali ke statenya sendiri), sedangkan bila pembeli menekan tombol $ maka state akan kembali ke state 0.

Dalam bentuk tabel gambar diatas dibisa dibuat sebagai berikut (State bertanda * merupakan acceptance state) :

Tabel State Diagram