FINITE STATE OTOMATA (FSA)

Finite Automata (FA) adalah model matematika untuk sistem komputasi dengan memori terbatas.

FA digunakan untuk:

• Pengolahan teks (regex, lexical analyzer)
• Sistem kendali otomatis
• Pendeteksi pola

A. Jenis FSA

1. Deterministic Finite Automata (DFA)
   Dari suatu state ada tepat satu state berikutnya untuk setiap symbol masukan yang diterima.
2. Non-deterministic Finite Automata (NFA)
   Dari suatu state ada 0, 1 atau lebih state berikutnya untuk setiap simbol masukan yang diterima.

Sebuah FA didefinisikan sebagai 5-tuple:

M = (Q, Σ, δ, q0, F)

• Q: Himpunan hingga dari state
• Σ: Himpunan hingga dari simbol input (alfabet)
• δ: Fungsi transisi, Q × Σ → Q
• q0: State awal (q0 ∈ Q)
• F: Himpunan state akhir (F ⊆ Q)

B. Cara kerja Finite Automata

1. 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
2. Finite Automata selalu dalam kondisi yang disebut state awal pada saat Finite Automata mulai membaca tape.
3. Perubahan state terjadi pada mesin ketika sebuah karakter berikutnya dibaca.
4. 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). FA untuk mengenali Bilangan Cacah

C. Graph Transisi

D. Himpunan State = Q

Q = {q₀ , q₁, q₂ , q₃ , q₄ , q₅}

1. State awal = q₀

2. State Akhir = F

F = {q4}