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.
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
2
|
#include
<stdio.h>
#include
<stdbool.h>
|
1. Pertama
kita deklarisan dulu DFA sebagai integer dengan nilai 0.
1
|
int dfa =
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
<stdio.h>
#include
<string.h>
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
Masukan Kalimat: abab
Diterima
Output 2 :
Masukan Kalimat: baba
Ditolak
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 :
Comments
Post a Comment