Finite automata
adalah mesin abstrak berupa sistem model matematika dengan masukan dan keluaran
diskrit yang dapat mengenali bahasa paling sederhana (bahasa reguler) dan dapat
diimplementasikan secara nyata.
1.
Finite
State Automata
• Model matematika
suatu sistem yang menerima input dan
output diskrit
• Mesin automata
dari bahasa Regular
• Tidak memiliki
tempat penyimpanan sehingga kemampuan
mengingat terbatas (contoh: elevator/lift)
• Aplikatif
berguna untuk merancang sistem nyata.
• Aplikasi
meliputi: analisis leksikal, text-editor, protokol komunikasi jaringan
(kermit) dan parity checker (pengecek
parity).
FSA didefinisikan
sebagai pasangan 5 tupel : (Q, ∑, δ, S, F). FSA atau AH (Automata
Hingga) didefinisikan
sebagai pasangan 5 Tupel M = (Q, ∑, δ, S, F).
Q : himpunan hingga state
∑ (Sigma) : himpunan hingga simbol input (alfabet)
δ (Delta) : 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
Contoh :
Seorang petani dengan seekor serigala, kambing dan seikat rumput berada pada suatu sisi sungai. Tersedia hanya sebuah perahu kecil yang hanya dapat dimuati dengan petani tersebut dengan salah satu serigala, kambing atau rumput. Petani tersebut harus menyeberangkan ketiga bawaannya kesisi lain sungai.
Seorang petani dengan seekor serigala, kambing dan seikat rumput berada pada suatu sisi sungai. Tersedia hanya sebuah perahu kecil yang hanya dapat dimuati dengan petani tersebut dengan salah satu serigala, kambing atau rumput. Petani tersebut harus menyeberangkan ketiga bawaannya kesisi lain sungai.
Tetapi jika petani
meninggalkan serigala dan kambing pada suatu saat, maka kambing akan
dimakan serigala. Begitu
pula jika kambing ditinggalkan dengan rumput, maka rumput akan dimakan oleh
kambing. Mungkinkah
ditemukan suatu cara untuk melintasi sungai tanpa menyebabkan kambing atau
rumput dimakan.
Jawab :
Tupel: M = (Q, ∑,
δ, S, F)
Q = {PKSR-Φ, SR-PK, PSR-K,
R-PSK, S-PKR, PKR-S, PSK-R, K-PSR, PK-SR, Φ-PKSR}
Σ =
{p, k, s, r}
S = PKSR – Φ
F =
{Φ-PKSR}
Ada dua jenis FSA, Finite State Automata
dapat berupa:
1. Deterministic Finite Automata (DFA)
Artinya: Dari
suatu state ada tepat satu state berikutnya untuk setiap simbol input yang
diterima. Deterministic
finite automata (DFA) M = (Q, ∑, δ, S, F), dimana :
Q :
himpunan state/kedudukan
∑ : himpunan simbol input
∂ : fungsi transisi,dimana ∂ ∈ Q x ∑ Q
S : State awal (initial
state)
F : himpunan state akhir
(Final State)
Language L(M) :
(x| ∂(S,x) di dalam F)
Penelusuran/Tracking:
Telusurilah,
apakah kalimat-kalimat berikut diterima DFA di atas:
abababaa, aaaabab
, aaabbaba
Jawab :
δ (q0,abababaa) ⇒ δ (q0,bababaa) ⇒ δ (q1,ababaa) ⇒
δ (q0,babaa) ⇒ δ (q1,abaa) ⇒ δ (q0,baa) ⇒ δ (q1,aa) ⇒
δ (q0,a) ⇒ q0
Tracking berakhir
di q0 (state AKHIR) ⇒
kalimat abababaa diterima
Kesimpulan :
Sebuah kalimat
diterima oleh DFA di atas jika tracingnya berakhir di salah satu state
AKHIR.
2. Nondeterministic Finite Automata (NDFA) / NFA
Artinya: Dari
suatu state bisa terdapat 0,1 atau lebih busur keluar (transisi) berlabel
simbol input yang sama. Non
Deterministic finite automata (NFA) M = (Q, ∑, δ, S, F), dimana :
Q : himpunan
state/kedudukan
∑ : himpunan simbol
input
∂ : fungsi
transisi, dimana ∂ ∈
Q x (∑ ⋃
ε) P(Q)
P(Q) : set of all
subsets of Q
S : State awal
(initial state)
F : himpunan state
akhir (Final State)
Language L(M) :
(x| ∂(S,x) di dalam F)
Ekuivalen antar DFA
Untuk suatu bahasa
regular, kemungkinan ada sejumlah Deterministic Finite Automata yang dapat
menerimanya. Perbedaannya hanyalah jumlah state yang dimiliki otomata-otomata
yang saling ekuivalen tersebut. Tentu saja, dengan alasan kepraktisan, kita
memilih otomata dengan jumlah state yang lebih sedikit. Dua
DFA M1 dan M2 dinyatakan ekuivalen apabila L(M1) = L(M2)
Reduksi Jumlah State
Reduksi dilakukan
untuk mengurangi jumlah state tanpa mengurangi kemampuan untuk menerima suatu
bahasa seperti semula (efisiensi). State pada FSA dapat direduksi apabila
terdapat useless state. Hasil dari FSA yang direduksi merupakan ekivalensi dari
FSA semula
Sasaran kita di
sini adalah mengurangi jumlah state dari suatu Finite State Automata, dengan
tidak mengurangi kemampuannya semula untuk menerima suatu bahasa.
Ada dua buah istilah baru yang perlu kita ketahui yaitu :
Ada dua buah istilah baru yang perlu kita ketahui yaitu :
1.
Distinguishable yang
berarti dapat dibedakan
:
Dua
state p dan q dari suatu DFA dikatakan indistinguishable apabila:
δ(q,w) ∈ F dan δ(p,w) ∈ F atau δ(q,w) ∉ F dan δ(p,w) ∉ F untuk semua w ∈ S*
δ(q,w) ∈ F dan δ(p,w) ∈ F atau δ(q,w) ∉ F dan δ(p,w) ∉ F untuk semua w ∈ S*
2.
Indistinguishable yang
berarti tidak dapat dibedakan.
Dua
state p dan q dari suatu DFA dikatakan distinguishable,
jika ada string w ∈ S* hingga: δ(q,w) Î δ(q,w) ∈F dan δ(p,w) ∉F
jika ada string w ∈ S* hingga: δ(q,w) Î δ(q,w) ∈F dan δ(p,w) ∉F
Pasangan dua buah
state memiliki salah satu kemungkinan : distinguishable atau indistinguishable
tetapi tidak kedua-duanya. Dalam hal ini terdapat sebuah relasi :
Jika p dan
q indistinguishable, dan q dan r indistinguishable maka p, r indistinguishable
dan p, q, r indistinguishable
Dalam melakukan
eveluasi state, didefinisikan suatu relasi :
Untuk Q yang
merupakan himpunan semua state D adalah himpunan
state-state distinguishable, dimana D ⊂ Q Nadalah himpunan
state-state indistinguishable, dimana N ⊂ Q maka x ∈ N jika x ∈ Q dan x ∉ D
source :
