Finite state Automata

Finite State Automata

Finite state automata 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.

Finite State Automata (FSA) adalah model matematika yang dapat menerima input dan mengeluarkan output yang memiliki state yang berhingga banyaknya dan dapat berpindah dari satu state ke state lainnya berdasarkan input dan fungsi transisi. Finite state automata tidak memiliki tempat penyimpanan/memory, hanya bisa mengingat state terkini. Pada FSA mesin mula-mula dalam state S0 dan menerima sederatan masukan yang dapat mengubahnya ke state-state berikutnya. Dalam FSA juga dikenal himpunan state-state tertentu yang disebut sabagai FINAL STATE. Perubahan dari satu state ke state berikutnya mengikuti sturan tertentu yang dirumuskan sebagai suatu FUNGSI transisi M. 

Secara formal FSA dapat didefinisikan sebagai TUPLE-5 : (K, V_T, M, S, Z) Dimana :

K   : himpunan hingga stata,

V_T  : himpunan hingga simbol input (alfabet)

M : fungsi transisi, menggambarkan transisi stata AH akibat pembacaan simbol input. (Fungsi transisi ini biasanya diberikan dalam bentuk tabel.)

S K  : stata awal

Z K  : himpunan stata penerima

Cara Kerja Finite State Automata
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).

Ada dua jenis Finite State Automata :

• Deterministic Finite Automata : transisi stata AH akibat pembacaan sebuah simbol bersifat tertentu. “Jika pada setiap state dari FSA tersebut apabila menerima input sebuah simbol maka HANYA ada SATU NEXT STATE yang mungkin dituju.” M(DFA) : K  V_T  K

• Non Deterministik Finite Automata : transisi stata AH akibat pembacaan sebuah simbol bersifat tak tentu. “Jika FSA tersebut menerima input simbol maka minimal ada satu state yang akan berpindah ke LEBIH DARI SATU NEXT STATE yang mungkin dituju.

M(AHN) : K  V_T 2^K

^{Contoh FSA}

Buatlah diagram transisi dari FSA yang didefinisikan sebagai : M = (K, V_T, M, S, Z) dimana :

S     ={S0, S1, S2, S3}

V_T ={ 0,1 }

K     ={S₀ , S₃ }

Dengan fungsi transisi M ada pada tabel transisi sebagai berikut:

Cara Kerjanya

Mula-mula dalam state S₀

Jika dari S₀ menerima 1 : akan ke State-S₁

Jika dari S₀ menerima 11 : akan ke State-S₁ lalu ke S₂

Jika dari S₀ menerima 0 : akan tetap di State- S₀

Jika dari S₀ menerima 10 : akan tetap kembali lagi State- S₀

Jika dari S₀ berturut-turut menerima masukan : 111, maka ia akan kembali ke- S₀

_REVERENSI

http://lisetyo.staff.gunadarma.ac.id/Downloads/files/42312/TEORI+BAHASA+DAN+OTOMATA+PERTEMUAN+KE-3.pdf

https://riskasimaremare.wordpress.com/2013/04/23/finite-state-automata/

https://septianandri11.wordpress.com/2012/09/13/finite-state-automatafsa-pada-bahasa-automata/

SEKIAN DARI SAYA , TERIMAKASIH :)