Finite State Automata

Finite State Automata

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

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 }

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. 

1. 0011 : diterima. 
2. 10010 : ditolak, karena banyaknya 0 ganjil 

• Diagram transisi-nya : 

DFA nya

Q = {q0 , q1 , q2 , q3 }

Σ = {0,1}

S = q0

F = { q0}

fungsi transisi.

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

• Contoh DFA lainnya : 

Nondeterministic Finite Automata

• Perbedaan dengan NFA: fungsi transisi dapat memiliki 0 atau lebih fungsi transisi
• G = ({q0 , q1 , q2 , q3, q4 }, {0,1}, δ ,  q0 , { q2 , q4}}

• String diterima NFA bila terdapat suatu urutan transisi berdasar input, dari state awal ke state akhir.
• Harus mencoba semua kemungkinan.
• Contoh : string 01001

Def 2. Dua buah FSA disebut ekuivalen apabila kedua FSA tersebut menerima bahasa yang sama.

Contoh : FSA yang menerima bahasa {an | n≥0 }

Def 3.  Dua buah state dari FSA disebut indistinguishable  (tidak dapat dibedakan)

apabila :

• δ(q,w)∈F sedangkan δ(p,w)∉F dan
• δ(q,w) ∉F sedangkan δ(p,w) ∈F untuk semua w ∈ Σ*

Def 4.  Dua buah state dari FSA disebut distinguishable  (dapat dibedakan) bila terdapat

w ∈ Σ* sedemikian hingga:

• δ(q,w)∈F sedangkan δ(p,w)∉F dan
• δ(q,w) ∉F sedangkan δ(p,w) ∈F untuk semua w ∈ Σ*

Prosedur menentukan pasangan status indistinguishable

1. Hapus semua state yang tak dapat dicapai dari state awal.

2. Catat semua pasangan state (p,q) yang distinguishable, yaitu {(p,q) | p ∈ F ∧ q ∉ F}.

3. Untuk setiap pasangan (p,q) sisanya, untuk setiap a∈ Σ,  tentukan δ(p,a) dan δ(q,a).

Contoh:

1. Hapus state yang tidak tercapai -> tidak ada.
2. Pasangan distinguishable (q0,q4), (q1,q4), (q2,q4), (q3,q4).
3. Pasangan sisanya (q0,q1), (q0,q2), (q0,q3), (q1,q2) (q1,q3) (q2,q3).

Daftar Pustaka

Rustamaji, Heru Cahya. 2004. TEORI BAHASA DAN AUTOMATA. diakses dari  http://dharmayanti.staff.gunadarma.ac.id/Downloads/files/8874/Modul_TBO-1.pdf, pada 6 Maret 2020.