Penerapan FSA, DFA(Deterministik Finite Automata), NFA(non deterministik Finite Automata), Ekuivalen antar DFA, Reduksi Jumlah State
Finite State Automata (FSA)
Finite Automata adalah model matematika sistem dengan masukan dan keluaran diskrit. Finite State Automata adalah model matematika yang dapat menerima inputan dan mengeluarkan output. Memiliki state berhingga banyaknya dan dapat berpindah dari satu ke yang lainnya sesuai dengan inputan dan fungsi transisi.
Contoh Sistem dengan state berhingga :
- Sistem elevator
- Mesin penjual minuman kaleng (vending machine)
- Pengatur lampu lalu lintas
- Sirkit switching di komputer dan telekomunikasi
- Lexical Analyzer
- Neuron Nets
Finite State Diagram (FSD)
Finite State Automata dapat dimodelkan dengan Finite State Diagram (FSD) dapat juga disebut State Transition Diagram.
Finite State Diagram terdiri dari:
1. Lingkaran menyatakan state
Lingkaran diberi label sesuai dengan nama state tersebut.
Adapun pembagian lingkaran adalah:
- Lingkaran bergaris tunggal berarti state sementara
- Lingkaran bergaris ganda berarti state akhir
2. Anak Panah menyatakan transisi yang terjadi
Label di anak panah menyatakan simbol yang membuat transisi dari 1 state ke state lain
1 anak panah diberi label start untuk menyatakan awal mula transisi dilakukan
Klasifikasi FSA
Ada dua jenis FSA :
•Deterministic finite automata (DFA)
Terdiri dari 1 transisi dari suatu state pada 1 simbol masukan. 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.
Contoh Kasus
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:
Ilustrasi
graf untuk DFA F adalah
sebagai berikut:
Apabila stata awal
•Non deterministik finite automata.(NFA)
Lebih dari 1 transisi dari suatu state dimungkinkan pada simbol masukan yang sama
Kedua finite automata tersebut mampu mengenali himpunan reguler secara presisi. Dengan demikian kedua finite automata itu dapat mengenali string-string yang ditunjukkan dengan ekspresi reguler secara tepat.
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.•Non deterministik finite automata.(NFA)
Lebih dari 1 transisi dari suatu state dimungkinkan pada simbol masukan yang sama
Kedua finite automata tersebut mampu mengenali himpunan reguler secara presisi. Dengan demikian kedua finite automata itu dapat mengenali string-string yang ditunjukkan dengan ekspresi reguler secara tepat.
Nondeterministic Finite Automata
(NFA) adalah salah satu bagian dari otomata berhingga atau Finite State
Automata (FSA). Pada Nondeterministic Finite Automata (NFA) dimungkinkan satu
simbol menimbulkan transisi ke lebih dari satu kondisi dan memberikan beberapa
kemungkinan gerakan sehingga keluarannya tidak dapat dipastikan. Selain itu
dimungkinkan juga terjadinya transisi spontan atau transisi –ε.
Nondeterministic Finite Automata
(NFA) didefenisikan sebagai M yang merupakan sebuah koleksi dari 5 obyek (Q , Σ
, s , F , ∆ ) dimana :
1. Q adalah sebuah himpunan hingga
dari kedudukan-kedudukan.
2. Σ adalah sebuah abjad masukan.
3. s adalah salah satu kedudukan di
dalam Q yang ditetapkan sebagai kedudukan permulaan.
4. F adalah sebuah koleksi dari
kedudukan-kedudukan yang diterima atau final (koleksi / himpunan dari kondisi
akhir).
5. ∆ adalah sebuah relasi pada (Q x
Σ) x Q dan dinamakan relasi transisi.
(Kelley, 1995: 46).
DFA dapat menuntun recognizer(pengenal) lebih cepat dibanding NDFA. Namun demikian, DFA berukuran lebih besar dibanding NDFA yang ekivalen dengannya. Lebih mudah membangun NDFA dibanding DFA untuk suatu bahasa, namun lebih mudah mengimplementasikan DFA diabnding NDFA.
Ekuivalensi
Antar Deterministic Finite Automata ( Reduksi )
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 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:
- Penerapan FSA :
·
Penerapan Konsep Finite State Automata
(FSA) pada Mesin Pembuat Minuman Kopi Otomatis
Finite
State Automata (FSA) merupakan tool yang sangat berguna untuk mengenal dan menangkap
pola dalam data. Finite State Automata (FSA) adalah model matematika yang dapat
menerima input dan mengeluarkan output yang memiliki state yang berhingga
banyaknya dan dapat berpindah dari satu state ke state lainnya berdasarkan
input dan fungsi transisi [1].
Pada
penelitian ini akan dimodelkan suatu penerapan konsep Finite State Automata
(FSA) pada suatu mesin pembuat minuman kopi otomatis. Penerapan konsep FSA
digunakan untuk mengenal dan menangkap pola dalam proses pembuatan minuman kopi
pada mesin pembuat minuman kopi otomatis.
Tujuan
dari penelitian ini adalah menerapkan konsep Finite State Automata (FSA) pada
aplikasi simulasi mesin pembuat minuman kopi otomatis dan menghasilkan suatu
aplikasi simulasi mesin yang dapat melakukan proses pembuatan minuman kopi dan
variasinya secara otomatis. Selain itu, pada penelitian ini akan di generate
suatu grammar untuk menghasilkan ke tujuh jenis minuman seperti yang telah
didiskusikan sebelumnya.
- Penerapan NFA:
·
Penerapan Konsep Non-Deterministic Finite
Automata (NFA) pada Aplikasi Simulasi Mesin Kopi Vending
Terdapat
penelitian terdahulu yang sejenis (Rizky Indah Melly E.P, 2012)mengenai
penerapan konsep finite state automata (FSA) mesin pembuat kopi otomatis. Akan
tetapi, pada penelitian tersebut belum diterapkan sistem pembayaran, beserta
variasi suhu dan ukuran gelas kopi yang dapat dipilih. Sehingga pada penelitian
ini akan dihasilkan aplikasi simulasi mesin kopi vending, yang dapat menangani
transaksi pembayaran cash serta membuat kopi sesuai pilihan variasi rasa, suhu,
dan ukuran gelas kopi yang diinginkan.
. Jenis state
diagram yang digunakan yaitu mealy machines dengan konsep Non-Deterministic
Finite Automata (NFA). Dengan mealy machines akan terlihat output yang dikeluarkan
pada setiap transisi antar state yang terjadi berdasarkan inputan yang diterima
dan state sebelumnya.
Daftar pustaka :
[1] Linz, Peter. An
Introduction to Formal Language and Automata. John and Bartlett Publisher
(2001).
Komentar
Posting Komentar