Pengertian dan Contoh Finite State Automata (FSA)

Definisi Finite State Automata (FSA) Pengertian Finite State Automata (FSA)

Finite State Automata (FSA) 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. Bahasa yang paling sederhana adalah bahasa reguler (tipe 3). Mesin yang bisa mengenalinya adalah Finite Automata. Finite Automata adalah mesin komputasi. Pada bahasan ini mesin komputasi yang dimaksud adalah mesin abstrak bukan mesin fisik, namun memadai untuk diimplementasikan secara nyata.

Pengertian FSA

Finite Automata adalah model matematika sistem dengan masukan dan keluaran diskrit. Finite State Automata adalah model matematika yang dapat menerima inputan dan mengeluarkan output. Memiliki state berhingga banyaknya dan dapat berpindah dari satu ke yang lainnya sesuai dengan inputan dan fungsi transisi.

Contoh Sistem dengan state berhingga :

Sistem elevator

Mesin penjual minuman kaleng (vending machine)

Pengatur lampu lalu lintas

Sirkit switching di komputer dan telekomunikasi

Lexical Analyzer

Neuron Nets

Finite State Diagram (FSD)

Finite State Automata dapat dimodelkan dengan Finite State Diagram (FSD) dapat juga disebut State Transition Diagram.

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

Klasifikasi FSA

Ada dua jenis FSA :

Deterministic finite automata (DFA) 

Terdiri dari 1 transisi dari suatu state pada 1 simbol masukan.

Non deterministik finite automata.(NFA)

Lebih dari 1 transisi dari suatu state dimungkinkan pada simbol masukan yang sama

Kedua finite automata tersebut mampu mengenali himpunan reguler secara presisi. Dengan demikian kedua finite automata itu dapat mengenali string-string yang ditunjukkan dengan ekspresi reguler secara tepat.

DFA dapat menuntun recognizer(pengenal) lebih cepat dibanding NDFA.

Namun demikian, DFA berukuran lebih besar dibanding NDFA yang ekivalen dengannya.

Lebih mudah membangun NDFA dibanding DFA untuk suatu bahasa, namun lebih mudah mengimplementasikan DFA diabnding NDFA.

Finite State Automata (FSA) adalah suatu mesin (bukan secara fisik) yang dapat menerima input dan output diskrit. Mesin tersebut memiliki karakteristik sbb:

• merupakan kelompok bahasa regular

• jumlah state berhingga

• input berpindah dari suatu state ke state lainnya

• tidak mempunyai tempat penyimpanan

Karena tidak memiliki tempat penyimpanan, maka FSA dianggap sebagai mesin otomata yang memiliki kemampuan paling rendah.

Mekanisme kerja FSA adalah sebagai berikut :

1. FSA terdiri dari satu atau beberapa state berhinga

2. Tiap-tiap state hanya dapat menyimpan 1 bit saja, sehingga apabila ada input baru, maka input sebelumnya akan terhapus.

3. Setiap state dapat melakukan transisi dari suatu state ke state berikutnya.

4. Transisi state di mulai dari state awal dan berakhir di state akhir.

5. Suatu input state dikatakan dapat diterima sebagai output FSA apabila telah sampai pada state akhir.

Diagram transisi FSA dapat digambarkan sebagai berikut:

Diagram Transisi FSA

Keterangan : 

q0 = state awal , q1 = state akhir, =transisi
FSA dibangun dengan 5 tupel : Q = himpunan state
e = himpunan simbol input
d = himpunan transisi
S = state awal
F = state akhir

Contoh penerapan bahasa dan automata dalam kehidupan sehari-hari:

1. Aplikasi Siri dan Cortana

2. Mesin ATM
3. Web Browser
4. Kalkulator

Automata adalah mesin abstrak yang dapat mengenali (recognize) dan menerima (accept) masukan (input) dari pengguna sehingga akan menghasilkan (generate) sebuah output tertentu.

Teori Automata sangan berkaitan erat dalam tata basa, karena mesin automata bekerja dengan mengenali masukan yang berstruktur seperti layaknya sebuah bahasa.

Bahasa dalam bentuk tulisan terdiri atas symbol-simbol satuan yang jika dikombinasikan akan mempunyai arti yang berbeda.

Contoh penggunaan automata dan bahasa dalah dalam aplikasi asisten pada smartphone, yaitu Siri dari Apple dan Cortana dari Microsoft.

Siri adalah perangkat lunak yang dikembangkan oleh perusahaan asal Amerika Serikat, Apple, yang menggunakan perintah atau input suara. Aplikasi ini diterapkan pada perangkat smartphone milik Apple, yaitu iPhone. Ketika pengguna iPhone memerintahkan secara suara, iPhone akan menangkap suara ini, merubahnya menjadi file biner dan kemudian mengirimnya melalui jaringan internet ke server Apple di Amerika Serikat. Di server ini, suara ini akan diolah menjadi perintah yang sesuai dengan keperluan pengguna.

Sama seperti Siri, Cortana adalah aplikasi perintah suara, dan aplikasi ini dikembangkan oleh Microsoft sebagai pesaing dari Siri. Prinsipekrja Cortana mirip dengan Siri. Cortana terdapat di perangkat yang menggunakan sistem operasi Windows 10.

Penggunaan mesin ATM merupakan contoh lain dalam teori bahasa dan automata. Suatu mesin ATM meminta dan mebaca input dari user, lalu mencocokkannya dalam database bank dan menghasilkan output berupa uang yang diminta atau keterangan lain.

Sumber Terkait:

Contoh FSA dalam kehidupan sehari-hari