UTS - FSA and Grammar

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

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

Secara formal FSA dapat didefinisikan sebagai TUPLE-5 : (Q, ∑, δ, S, F). 
Q : himpunan hingga state 
∑ : himpunan hingga simbol input (alfabet) 
δ : fungsi transisi, menggambarkan transisi state FSA akibat pembacaan simbol input. Fungsi transisi ini biasanya diberikan dalam bentuk tabel. 
S : state awal
F : himpunan state akhir

Contoh :

2. Regular Grammer

Grammar adalah bentuk abstrak yang dapat diterima (accept) untuk membangkitkan suatu kalimat otomata berdasarkan suatu aturan tertentu.

Grammar G didefinisikan sebagai pasangan 4 tuple : V , T , P, dan S, dan dituliskan sebagai G(V , T , P, S), dimana :
V       : himpunan  simbol-simbol variable / non terminal
T       : himpunan simbol-simbol terminal
P       : himpunan produksi 
S    : simbol awal (atau simbol start)

Contoh Kasus Grammer