Finite State Automata (fsa)

• Model matematika yang dapat menerima input dan mengeluarkan output
• Memiliki state yang berhingga banyaknya dan dapat berpindah dari satu state ke state lainnya berdasar input dan fungsi transisi
• Tidak memiliki tempat penyimpanan/memory, hanya bisa mengingat state terkini.
• Mekanisme kerja dapat diaplikasikan pada : elevator, text editor, analisa leksikal, pencek parity.

0

1

0

1

1

0

1

FA

Contoh pencek parity ganjil :
Misal input : 1101
         Genap 1 Ganjil 1 Genap 0 Genap 1 Ganjil
         diterima mesin
Misal input : 1100
         Genap 1 Ganjil 1 Genap 0 Genap 0 Genap
         ditolak mesin
Def 1. Finite State Automata dinyatakan oleh 5 tuple
           M=(Q , Σ , δ , S , F )
              Q = himpunan state
              Σ = himpunan simbol input
              δ = fungsi transisi δ : Q × Σ
              S = state awal / initial state , S ∈ Q
              F = state akhir, F ⊆ Q
Contoh diatas, 
Q = {Genap, Ganjil} 
Σ = {0,1}  
S = Genap 
F = {Ganjil }

δ	0	1
Genap	Genap	Ganjil
Ganjil	Ganjil	Genap

atau

δ(Genap,0) = Genap
δ(Genap,1) = Ganjil
δ(Ganjil,0) = Ganjil
δ(Ganjil,1) = Genap
Jenis FSA
Deterministic Finite Automata (DFA) : dari suatu state ada tepat satu state berikutnya untuk setiap simbol masukan yang diterima
Non-deterministic Finite Automata (NFA) : dari suatu state ada 0, 1 atau lebih state berikutnya untuk setiap simbol masukan yang diterima

Deterministic Finite Automata

• Contoh : pengujian parity ganjil.
• Contoh lain : Pengujian untuk menerima bit string dengan banyaknya 0 genap,
  serta banyaknya 1 genap.
  ♦ 0011 : diterima.
  ♦ 10010 : ditolak, karena banyaknya 0 ganjil
• Diagram transisi-nya :

• DFA nya
  Q = {q0 , q1 , q2 , q3 }
  Σ = {0,1}
  S = q0
  F = { q0}
  fungsi transisi

δ	0	1
q0	q2	q1
q1	q3	q0
q2	q0	q3
q3	q1	q2

• Contoh lain DFA : Variabel dalam bahasa pascal diawali oleh huruf (besar/kecil),
  dan diikuti dengan huruf atau angka.

• Contoh DFA lainnya :