Finite State Otomata || Nur Anisah Fadhilah - 202131020

                                                                                                   Institut Teknologi PLN Jakarta

Dosen : DINE TIARA KUSUMA, S.T., M.Kom

FINITE STATE OTOMATA

Finite State Automata (FSA)

Finte State Automata merupakan tool yang sangat berguna dalam perancangan lexical analyzer, yaitu bagian dari kompilator yang mengelompokkan karakter - karakter kedalam sebuah token, yang berupa unit terkecil seperti nama, variabel, dan keyword.

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

• Finite State Automata (FSA) atau Automata Hingga (AH) di definisikan sebagai pasangan 5 tupel => M = (Q, Σ, δ, S, F), dimana : 

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 ∈ Q : State awal

F ⊆ Q : Himpunan state akhir

Pada gambar FSA dibawah : 

1. Mesin ini memiliki 6 state yaitu (q0, q1, q2, q3, q4, q5)
2. State awal yaitu q0
3. Sedangkan state akhir yaitu q3, q
4. Simbol input adalah (a, d, u)

Contoh Finite State Automata (FSA) Untuk Mengecek Parity Ganjil 

Keterangan :

• Q : { Gnp, Gjl }
• Σ : { 0, 1 }
• S : Gnp
• F : Gjl

Digram Transisinya :

Definisi Formal Finite State Automata

M = (Q, Σ, δ, S, F), dimana :

Q : Himpunan state

Σ : Abjad, Himpunan simbol input (masukan)

δ : Fungsi transisi, δ : Q x Σ => Q

S ∈ Q : State awal (Initial State)

F ⊆ Q : Himpunan state akhir (Final State)

 

Finite State Automata (FSA), yaitu Deterministic Finite Automata (DFA / DFSA) dan Non-Deterministic Finite Automata (NFA / NFSA).

• Deterministic Finite Automata (DFA / DFSA) : Pada setiap input, hanya ada satu keadaan (state) tujuan dari keadaan saat ini.
• Non-Deterministic Finite Automata (NFA / NFSA) : Pada setiap input terdapat lebih dari satu keadaan tujuan dari keadaan saat ini.

Deterministic Finite Automata (DFA / DFSA) terdiri atas 5 tupel, yaitu A = (Q, Σ, δ, Q0, F)

Notasi Lain Deterministic Finite Automata (DFA / DFSA) :

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