Penerapan FSA (Finite
State Automata)
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. Sedangkan Finite
State Automata (FSA) adalah model matematika dari sistem dengan masukan dan
keluara nberupa nilai diskrit.
Pengaplikasian Finite Automata dapat ditemukan
pada algoritma- algoritma yang digunakan untuk pencocokkan string pada
perangkat lunak editor teks dan perangkat lunak pengecekan ejaan, serta dapat
ditemui juga pada penganalisa sintaks yang digunakan oleh Assemblers atau
Compilers.
Automata memiliki suatu alur khusus dan unik
untuk setiap kata yang akan dikenali atau diterima. Jika suatu alur berakhir
pada suatu state yang disebut sebagai Final State atau Accepting State, maka
kata yang ditelusuri tersebut dikatakan dikenali oleh automata.
Komponen dasar yang dimilik ioleh Finite
Automata adalah Alphabet yaitu Himpunan symbol/ lambang yang dikenali. Himpunan
Alfabet diwakili dengan ∑ jika dan hany ajika ∑ merupakan himpunan symbol
yang bersifat tetap dan bukan merupakan himpunan kosong. Contoh umum dari
Alphabet adalah 26 (dua puluh enam) huruf yang dikenali dalam bahasa Indonesia
ataupun rangkaian karakter ASCII, yang merupakan rangkaian standar dari kode-
kode komputer. Sedangkan sebuah word, yang disebutkan juga string atau sentence
adalah rangkaian satu atau lebih alphabet yang telah dinyatakan
sebelumnya. Rangkaian word itu sendiri disebut bahasa (language), yang diwakili
dengan L.
Berikut ini adalah contoh Alphabet beserta words
yang dapat dibentuknya :
- ∑ = {a, b}, maka contoh words yang dapat dibentuknya
yaitu“aab”, “abab”, “a”, “bbbbbb”, dan lain- lain.
- ∑ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9},maka contoh words
yang dapat dibentuknya yaitu“26498098”, “100103”, “0000”, dan lain- lain.
Lebih lanjut, Concatenation adalah proses
menggabungkan dua buah words menjadi satu word baru, yaitu terdiri dari
rangkaian alphabet dari word pertama dan disambung dengan rangkaian alphabet
dari word ke-dua.
∑ = {a, b}, words = “aaa” dan y = “bbb”dimana
setiap a merupakan anggota himpunan ∑, a ∈ ∑ dan setiap b anggota himpunan ∑,
b ∈ ∑. Maka,
gabungan atau concatenation x dan y, dinyatakan dengan x,y = “aaabbb”.
Setelah memiliki pemahaman diatas, maka definisi
dari sebuah Finite Automata dapat ditetapkan sebagai suatu model Matematis dari
sebuah mesin yang menerima suatu rangkaian words tertentu yang mengandung
alphabet ∑. Setiap FSA memiliki:
- Himpunan berhingga (finite) status (state): Satu buah
status sebagai status awal (initial state), biasa dinyatakan q0. Beberapa buah
status sebagai status akhir (final state).
- Himpunan berhingga symbol masukan.
- Fungsitransisi:
- Menentukan status berikutnya dari setiap pasang status
dan sebuah symbol masukan.
Berikut adalah contoh penerapan FSA dalam sebuah
game
Q ={Stage 1, Stage 2,
Stage 3, Stage 4, Stage 5} himpunan state .
∑ ={Benar, Salah}
himpunan simbol input.
δ = fungsi transisi,
S = Gnp (Stage 1).
F = {Stage 5} (Final) himpunan state AKHIR.
Penerapan DFA
(Deterministic Finite Automata)
Deterministic
Finite Automaton disingkat menjadi “DFA” dan juga biasa dikenal
sebagai Deterministic Finite Acceptor (DFA), Deterministic Finite
State Machine (DFSM), atau Deterministic Finite State Automaton (DFSA).
DFA
merupakan teori komputasi dan cabang dari ilmu komputer teoritis. DFA
adalah Finite-state Machine atau mesin keadaan terbatas yang
menerima atau menolak string dari simbol dan hanya
menghasilkan perhitungan unik dari otomata untuk setiap string yang
di masukan.
Otomata berhingga deterministic atau
DFA (Deterministic Finite Automata) adalah FSA(finite state automata)
yang memiliki stata penerima tepat satu stata untuk setiap simbol masukan.
Contoh
Penerapan Kasus DFA
Penulis memberikan contoh untuk DFA F(K,VT,M,S,Z) ,
dimana:
· K = {S, A, B}
· VT = {a, b}
· S = {S}
· Z = {B}
M diberikan dalam
tabel berikut:
FA-TRANSISI
Ilustrasi graf untuk DFA F adalah
sebagai berikut:
Ilustrasi graf untuk DFA F
Apabila stata awal S diberi
masukan a maka akan bergerak ke stata A, stata A diberi
masukan b maka akan bergerak ke stata B (stata
penerima). Yang artinya DFA tersebut apabila diberi masukan string ab maka
masukan tersebut diterima. Lalu masukan apalagi yang diterima?
Bagaimana
jika kita tulis DFA tersebut menggunakan Bahasa C untuk mengetahaui kalimat apa
saja yang diterima.
Tulis header yang
akan kita gunakan, yaitu:
1.
Pertama kita deklarisan dulu DFA sebagai integer dengan nilai
0.
2. Buat fungsi pertama
yaitu apabila Stata S diberi masukan a maka akan bergerak ke stata
selanjutnya stata A dengan menukar nilai DFA menjadi 1 dan
apabila diberi masukan selain a maka nilai DFA tetap 0.
|
1
2
3
4
5
6
7
|
void S(char c)
{
if
( c == 'a' )
dfa
= 1;
else
dfa
= 0;
}
|
3. Buat fungsi selanjutnya yaitu apabila
stata A diberi
masukan b maka akan bergerak ke stata selanjutnya (stata B)
dengan mengubah nilai DFA menjadi 2 dan apabila diberi masukan selain a maka
nilai-nilai DFA tetap 1.
|
1
2
3
4
5
6
7
|
void Stata1(char c)
{
if
(c == 'b' )
dfa
= 2;
else
dfa
= 1;
}
|
4. Fungsi terakhir adalah apabila stata B diberi
masukan a maka akan kembali ke stata B dengan
menukar nilai DFA menjadi 1 dan apabila diberi masukan selain a maka
nilai-nilai DFA tetap 2.
|
1
2
3
4
5
6
7
|
void Stata2(char c)
{
if
(c == 'a' )
dfa
= 1;
else
dfa
= 2;
}
|
5.
Selanjutnya deklarasikan nilai int DFA serta string untuk
menampung pergerakan sebagai nilai tukar DFA.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
int diterima(char
str[])
{
int
i, len = strlen(str);
for
( i=0; i < len; i++) {
if
(dfa == 0)
S(str[i]);
else
if (dfa == 1)
Stata1(str[i]);
else
if (dfa == 2)
Stata1(str[i]);
else
return
0;
}
|
6. Buat Fungsi stata penerima, yaitu stata B (2).
|
1
2
3
4
5
|
if(dfa == 2)
return
1;
else
return
0;
}
|
7.
Buat fungsi utama untuk membaca string dan memproses string tersebut
apakah diterima atau tidak berdasarkan fungsi yang telah kita buat sebelumnya.
|
1
2
3
4
5
6
7
8
9
10
11
|
int main()
{
char
str[10];
printf("Masukan
Kalimat: ");
gets(str);
if
(diterima(str))
printf("\nDiterima\n");
else
printf("Ditolak\n");
return
0;
}
|
Program:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
#include
#include
int dfa = 0;
void S(char c)
{
if
( c == 'a' )
dfa
= 1;
else
dfa
= 0;
}
void Stata1(char c)
{
if
(c == 'b' )
dfa
= 2;
else
dfa
= 1;
}
void Stata2(char c)
{
if
(c == 'a' )
dfa
= 1;
else
dfa
= 2;
}
int diterima(char
str[])
{
int
i, len = strlen(str);
for
( i=0; i < len; i++) {
if
(dfa == 0)
S(str[i]);
else
if (dfa == 1)
Stata1(str[i]);
else
if (dfa == 2)
Stata1(str[i]);
else
return
0;
}
if(dfa
== 2)
return
1;
else
return
0;
}
int main()
{
char
str[10];
printf("Masukan
Kalimat: ");
gets(str);
if
(diterima(str))
printf("\nDiterima\n");
else
printf("Ditolak\n");
return
0;
}
|
Output 1 :
Masukan Kalimat: abab
Diterima
Output 2 :
Masukan Kalimat: baba
Ditolak
Penerapan NFA
(Non-deterministic Finite Automata)
Salah satu penerapan NFA
adalah dalam aplikasi simulasi Mesin Kopi Vending
Rancangan State Diagram
yang Dibuat
Pada gambar state
diagram diatas dapat dilihat inputan uang yang diterima yaitu x
(lembar uang Rp 5.000) dan y (lembar uang Rp 10.000). Setiap kali
dimasukkan uang, akan terjadi transisi pada state A (Saldo Rp 0), B (Saldo Rp
5.000), C (Saldo Rp 10.000), dan D (Saldo
Rp 15.000). Ketika saldo sudah mencapai
Rp 15.000, tidak dapat diterima inputan uang lagi, sehingga mesin akan
mengeluarkan output langsung sesuai dengan inputan uang x atau y yang
dimasukkan. Setelah dimasukkan uang, dapat diinput ukuran gelas kopi yang
diinginkan, yaitu e (memilih gelas kecil), f (memilih
gelas sedang), dan g (memilih gelas besar).
Mesin akan mengeluarkan kembalian jika ada. Sebaliknya jika tidak
ada kembalian, output yang dikeluarkan bernilai 0
(NULL). Selain output, terdapat juga inputan 0 (NULL)
dimana state dapat berpindah langsung ke state
selanjutnya tanpa menerima inputan apa-apa. Setelah memilih ukuran gelas, dapat
diinput variasi rasa kopi yang diinginkan,
antara lain i (memilih espresso), j
(memilih americano), k (memilih caffee latte), l (memilih
cappuccino), m (caffee macchiatto), dan n (memilih
caffee mocha). Inputan gula kemudian akan ditambahkan secara
otomatis sebagai salah satu bahan utama untuk membuat
kopi. Terdapat juga bahan ekstra yang dapat diinput
maksimal sebanyak 2 kali, yaitu o (memilih
gula), p (memilih kopi), q (memilih susu),
dan r (memilih coklat). Selanjutnya, mesin
akan dimasukkan inputan s (menambahkan sedikit
air) untuk melarutkan bahan-bahan yang dicampurkan pada kopi,
dan t (aduk) untuk mengaduk kopi. Setelah
itu dapat dipilih suhu kopi yang
diinginkan, yaitu u (memilih hot) dan v
(memilih iced). Jika ingin membatalkan inputan
variasi rasa kopi yang dipilih, dapat diinput
h (reset) untuk kembali mengulang inputan
ke state H. Sedangkan jika ingin memproses inputan,
dapat diinput w (proses) untuk membuat kopi. Mesin
kemudian akan mengeluarkan output bernilai 1
(mengeluarkan kopi) dan kembali ke state awal untuk memproses transaksi
pembelian kopi yang baru.
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.
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 :
1. Distinguishable yang berarti dapat dibedakan.
2. Indistinguishable yang berarti tidak dapat
dibedakan.
Dua DFA M1 dan M2 dinyatakan ekivalen apabila
L(M1) = L(M2)
Reduksi Jumlah State
Reduksi Jumlah State Pada FSA
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
Pasangan Statedapat
dikelompokkan berdasarkan:
1. Distinguishable
State (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*
2. Indistinguishable
State (tidak dapat dibedakan)
Dua
state p dan q dari suatu DFA dikatakan distinguishable jika ada
string w ÃŽ S* hingga:
δ(q,w) Î F
dan δ(p,w) ∉ F
Reduksi Jumlah State Pada FSA – Relasi
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 yg merupakan himpunan semua state
D adalah himpunan
state-state distinguishable, dimana D Ì Q
N adalah
himpunan state-state indistinguishable, dimana N Ì Q
maka x
ÃŽ N jika x ÃŽ Q dan x ∉ D
Reduksi Jumlah State Pada FSA – Step
Langkah - langkah untuk
melakukan reduksi ini adalah :
Hapuslah semua state yg
tidak dapat dicapai dari state awal (useless state)
Buatlah semua pasangan
state (p, q) yang distinguishable, dimana p ÃŽ F dan q ∉ F. Catat semua pasangan-pasangan state tersebut.
Cari state lain yang
distinguishable dengan aturan: Untuk
semua (p, q) dan semua a ÃŽ ∑, hitunglah δ (p, a) = pa dan δ (q, a) =
qa . Jika pasangan (pa, qa) adalah pasangan state yang
distinguishable maka pasangan (p, q) juga termasuk pasangan yang
distinguishable.
Semua pasangan state yang
tidak termasuk sebagai stateyang distinguishable merupakan state-state
indistinguishable.
Beberapa state yang
indistinguishable dapat digabungkan menjadi satu state.
Sesuaikan transisi dari
state-state gabungan tersebut.
Reduksi Jumlah State Pada FSA - Contoh
Sebuah Mesin DFA
- State q5
tidak dapat dicapai dari state awal dengan jalan apapun (useless
state). Hapus state q5
- Catat
state-state distinguishable, yaitu :
q4 ÃŽ F sedang q0, q1, q2, q3 ∉ F sehingga pasangan
(q0, q4) (q1, q4) (q2, q4) dan (q3, q4) adalah
distinguishable.
- Pasangan-pasangan
state lain yang distinguishable diturunkan berdasarkan pasangan dari
langkah 2, yaitu :
- Untuk pasangan (q0, q1)
δ(q0, 0) = q1 dan δ(q1,
0) q2 Ã belum teridentifikasi
δ(q0, 1) = q3 dan δ(q1,
1) = q4 Ã (q3, q4) distinguishable
maka (q0, q1) adalah distinguishable. \
- Untuk
pasangan (q0, q2)
δ(q0, 0) = q1 dan δ(q2,
0) = q1 Ã belum teridentifikasi
δ(q0, 1) = q3 dan δ(q2,
1) = q4 Ã (q3, q4) distinguishable
maka (q0, q2) adalah distinguishable.
- Setelah
diperiksa semua pasangan state maka terdapat state-state yang
distinguishable : (q0,q1), (q0,q2), (q0,q3), (q0,q4),
(q1,q4), (q2,q4), (q3,q4). Karena berdasarkan relasi-relasi
yang ada, tidak dapat dibuktikan (q1, q2), (q1, q3) dan (q2, q3)
distinguishable, sehingga disimpulkan pasangan-pasangan state
tersebut indistinguishable.
- Karena q1
indistinguishable dengan q2, q2 indistinguishable dengan q3,
maka dapat disimpulkan q1, q2, q3 saling indistinguishable dan dapat
dijadikan satu state.
- Berdasarkan
hasil diatas maka hasil dari DFA yang direduksi menjadi:
Sumber :
