FINITE STATE AUTOMATA
Finite 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. FSA didefinisikan sebagai pasangan 5 tupel : (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 (Start) F : himpunan state AKHIR (Final) Contoh : FSA untuk mengecek parity ganjil Q ={Gnp, Gjl} himpunan state ∑ ={0,1} himpunan simbol input δ = fungsi transisi, S = Gnp (Start) F = {Gjl} (Final) himpunan state AKHIR (ingat untuk himpunan harus ditulis di dalam {} ) dari diagram tersebut Contoh Bahasa/L(m) yang diterima adalah : 0110 (karena state akhirnya adalah finalnya ...