Finite State Automata (FSA)

 "Finite State Automata"

        FSA (Finite State Automata) merupakan tool yang sangat bergunadalam perancangan lexical analyzer, yaitu bagian dari kompilator yang mengelompokan karakter-karakter kedalam sebuah token, yang berupaunit terkecil seperti nama, variabel, dan keyword. 

        FSA dipakai untuk penganalisa leksikal dan dipakai juga dalam text editor, pemrosesan teks, dan program file-searching.

FSA atau AH (Automata Hingga) didefinisikan sebagai pasangan 5 tupel → M = (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

• Mesin ini memiliki 6 state : (q0,q1,q2,q3,q4,q5). 

• State awal q0, • Sedangkan q3 dan q4 adalah state akhir, dan 

• Simbol input adalah (a,d,u)

Contoh Finate State Automata : 

•Contoh : FSA untuk mengecek parity ganjil 

•Q ={Gnp, Gjl} 

•∑ = {0,1} 

•S = Gnp 

•F = Gjl

FSA dibagi menjadi 2 :

1. Deterministic (DFA) : Pada setiap input, hanya ada satu keadaan (state) tujuan dari keadaan saat ini.

2. Non deterministic (NFA) : Pada setiap input terdapat lebih dari satu keadaan tujuan dari keadaan saat ini.

"Deterministic Finate Automata (DFA)"

DFA, terdiri atas 5 tuple, yaitu : A = (Q, Σ, δ, q0, F) 

Notasi Lain DFA : 

1. Diagram Transisi / State Diagram 

• Tiap keadaan merupakan simpul 

• Tiap keadaan q ∈ Q dan tiap simbol a ∈ Σ, dituliskan sebagai δ(q,a) = p. Artinya, diagram transisi memiliki panah dari q ke p, yang berlabel a. 

• Keadaan awal (q0 ) ditandai dengan adanya panah tanpa sumber. 

• Simpul yang menjadi keadaan final ditandai dengan lingkaran bergaris tepi ganda 

2. Tabel Transisi 

• Representasi daftar dari suatu fungsi 

• Baris menunjukkan keadaan dan kolom menunjukkan input. 

• Isi dari baris menunjukkan keadaan q dan isi dari kolom input a menunjukkan keadaan δ(q,a)