Judul Psting : Makalah Finite State Automata
Makalah Finite State Automata
Finite State Automata
OLEH
KELOMPOK 1
FAHMI RAHMAT AZIS
RINALDI SYARFIANTO
RAE AWALIAGUS RIDWANA
TEKNIK INFORMATIKA
FAKULTAS SAINS TEKNOLOGI
UIN SUSKA RIAU
2014/2015
KATA PENGANTAR
Assalamu’alaikum warahmatullahi wabarakatuh.
Puji dan syukur kami panjatkan ke hadirat Allah SWT atas segala berkat, rahmat, taufik, serta hidayah-Nya yang tiada terkira besarnya, sehingga penulis dapat menyelesaikan makalah dengan judul ”Finite State Automata (FSA)”. tepat pada waktunya.
Tugas ini ditujukan untuk memenuhi tugas mata kuliah Teori Bahasa dan Otomata. Dalam penyusunannya, penulis memperoleh banyak bantuan dari berbagai pihak, karena itu penulis mengucapkan terima kasih kepada Teman-teman yang telah membantu Penulis dalam menyelesaikan makalah ini .
Penulis menyadari bahwa makalah ini masih banyak kekurangan dan kelemahannya, baik dalam isi maupun sistematikanya. Hal ini disebabkan oleh keterbatasan pengetahuan dan wawasan penulis. Oleh sebab itu, penulis sangat mengharapkan kritik dan saran untuk menyempurnakan makalah ini.
Akhirnya, penulis mengharapkan semoga makalah ini dapat memberikan manfaat, khususnya bagi penulis dan umumnya bagi pembaca.
Akhir kata penulis berharap agar makalah ini bermanfaat bagi semua pembaca.
Pekanbaru, Maret 2015
Tim Penulis
Bab 1
Pendahuluan
1.1 Latar Belakangan
Teori bahasa dan otomata merupakan salah satu mata kuliah yang wajib dijurusan-jurusan informatika maupun ilmu komputer. Diasumsikan para pembaca telah terbiasa dengan notasi-notasi yang digunakan disini, misalnya mengenai hinpunan, yang telah diperoleh dari kuliah-kuliah sebelumnya. Meskipun demikian bagi mereka diluar disiplin informatika dapat pula segera memahaminya karena telah diusahakan untuk sebisa mungkin memberikan penjelasan yang memadai untuk setiap hal baru yang disampaikan.
Dalam teori bahasa dan otomata terdapat salah satu materi berjudul Finite State Automata (FSA). Dimakalah ini kami akan fokus untuk menjelaskan berbagai hal mengenai FSA. Sub-sub dari FSA ini seperti Deterministic Finite Automata (DFA), Non- deterministic Finite Automata,ekuivalensi antar Deterministic Finite Automata, dan reduksi jumlah State pada Finite State Automata juga akan kami jelaskan.
1.2 Rumusan Masalah
1. Bagaimana penerapan Finite State Automata ?
2. Jelaskan tentang Deterministic Finite Automata !
3. Jelaskan tentang Non- deterministic Finite Automata !
4. Jelaskan tentang ekuivalensi antar Deterministic Finite Automata !
5. Jelaskan tentang reduksi jumlah State pada Finite State Automata !
Bab 2
Pembahasan
2.1 Penerapan Finite State Automata
FiniteState Automata/state otomata berhingga, selanjutnya kita tersebut sebagai FSA, bukanlah mesin fisik tetapi suatu model matematika dari suatu sistem yang menerima input dan output diskrit. Finite state automata memiliki state ke state lain. Perubahan state ini dinyatakan oleh fungsi transisi. Jenis otomata ini tidak memiliki tempat penyimpanan sehingga kemampuan ‘mengingatnya’ terbatas. Mekanisme kontrol pada suatu elevator / lift adalah contoh yang bagus untuk suatu otomata. Mekanisme tersebut tidak ‘mengingat’ semua permintaan sebelumnya tetapi hanya posisi lift saat itu pada suatu lantai, pergerakan (keatas atau bawah). Dan sekumpulan permintaan yang belum terpenuhi. Dalam ilmu komputer kita akan menemui banyak contoh dari sistem finitestate automata. teori mengenai finitestate automata adalah suatu tool yang berguna untuk merancang sistem tersebut. Mekanisme kerja suatu finitestate automata bisa diaplikasikan pada analisis leksikal, text-editor, protokol komunikasi jaringan (misal protokol kermit), dan pendek pariti.
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 ∈ Q | | |||||||
| S = state awal / initial state , | | ||||||||
| 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.
2.2 Deterministic Finite Automata
Contoh : pengujian parity ganjil.
Contoh lain : Pengujian untuk menerima bit string dengan banyaknya 0 genap, serta banyaknya 1 genap.
0011 : diterima.
10010 : ditolak, karena banyaknya 0 ganjil
Diagram transisi-nya :
DFA nya
Q = {q0 , q1 , q2 , q3 }
Σ = {0,1}
S = q0
F = { q0}
Fungsitransisi
| | δ | 0 | 1 | | | |
| | q0 | q2 | q1 | | | |
| | q1 | q3 | q0 | | | |
| | q2 | q0 | q3 | | | |
| δ( q0,011)= δ( | q3 | q1 | q2 | | | |
| q2,11) =δ( q3 | ,1)= q2 | Ditolak | | |||
δ( q0,1010)= δ( q1,010) =δ( q3,10)=δ( q2,0)= q0 Diterima
Contoh lain DFA : Variabel dalam bahasa pascal diawali oleh huruf (besar/kecil), dan diikuti dengan huruf atau angka.
2.3 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)
Prosedur Reduksi FDA
1. Tentukan pasangan status indistinguishable.
2. Gabungkan setiap group indistinguishable state ke dalam satu state dengan relasi pembentukan group secara berantai : Jika p dan q indistingishable dan jika q dan r indistinguishable maka p dan r indistinguishable, dan p,q serta r indistinguishable semua berada dalam satu group.
3. sesuaikan transisi dari dan ke state-state gabungan.
Contoh
1. pasangan status indistinguishable (q1,q2), (q1,q3) dan (q2,q3).
2. q1,q2,q3ketiganya dapat digabung dalam satu state q123
3. Menyesuaikan transisi, sehingga DFA menjadi
2.4 Ekuivalensi antar Deterministic Finite Automata
Misalkan terhadap 2 buah Deterministic Finite Automata, M1 dan M2, yang masing masing menerima bahasa L(M1) dan L(M2). Jika L(M1) = L(M2) maka 2 DFA tersebut dikatakan ekivalen. Sebagai contoh DFA M1 dan M2 memiliki diagram transisi seperti pada gambar 3.5 dan 3.6
2.5 Reduksi Jumlah State Pada Finite State Automata
Untuk suatu bahasa regular kemungkinan ada sejumlah DFA yang dapat menerimanya. Perbedaannya umumnya adalah pada jumlah state yang dimiliki oleh otomata-otomata yang saling ekivalen tersebut.
Tentunya secara praktis FSA dengan jumlah state yang lebih sedikit merupakan FSA yang paling efisien.
Untuk mendapatkan FSA yang efisien maka perlu dievaluasi dan direduksi jumlah state dari FSA tersebut dengan tidak mengurangi kemampuan semula dalam menerima suatu bahasa.
Setiap pasangan state didalam suatu FSA dapat dikelompokan atas :
· indistinguishable state
· distinguishable state
Distinguishable state adalah pasangan state yang dapat dibedakan, sedangkan indistinguishable state adalah pasangan state yang tidak dapat dibedakan.
Untuk state-state yang indistinguishable pada prinsipnya dapat digabungkan menjadi satu state. Reduksi jumlah state dapat dilakukan dengan pendekatan tersebut.
InDistinguishable State
Dua buah state p dan q dari sebuah FSA dikatakan indistinguishable jika :
δ (q, w) Î F begitu pula δ (p, w) Î F
dan
δ (q, w) ÏF begitu pula δ (p, w) ÏF
untuk semua w Î ∑*
Distinguishable State
Dua buah state p dan q dari sebuah FSA dikatakan distinguishable jika ada string w Î ∑* sedemikian sehingga :
δ (q, w) Î F sedangkan δ (p, w) Ï F
Relasi-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 juga indistinguishable
maka p, q, dan r indistinguishable
Dalam melakukan eveluasi state, didefinisikan suatu relasi :
Untuk Q adalah 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
Implementasi reduksi
Implementasi reduksi state dari suatu FSA dapat dilakukan sebagai berikut :
- Hapuslah semua state tidak dapat dicapai dari state awal (useless state)
- Indentifikasi state-state yang indistinguishable dan gabungkan
Secara lebih detil tahapan-tahapanya adalah sebagai berikut :
1. Hapuslah semua useless state
2. Buatlah semua pasangan state (p, q) yang distinguishable, dimana p Î F dan q ÏF. Catat semua pasangan-pasangan state tersebut.
3. Untuk semua state lakukan pencarian state lainnya yang distinguishable dengan aturan:
“Untuk semua (p, q) dan semua a Î ∑, hitunglah δ (p, a) = padan δ (q, a) = qa . Jika pasangan (pa, qa) adalah pasangan state yang distinguishable maka pasangan (p, q) juga termasuk pasangan yang distinguishable.
4. Semua pasangan state yang tidak termasuk sebagai state yang distinguishable, adalah state-state indistinguishable.
5. Beberapa state yang indistinguishable dapat digabungkan menjadi satu state.
6. Sesuaikan transisi dari state-state gabungan tersebut.
Sebagai contoh adalah sebagai berikut :
Secara bertahap dilakukan reduksi sebagai berikut :
1. State q5 tidak dapat dicapai dari state awal dengan jalan apapun (useless state).
Hapus state q5
2. 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.
3. 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.
· Untuk pasangan (q0, q3)
δ(q0, 0) = q1 dan δ(q3, 0) = q2 à belum teridentifikasi
δ(q0, 1) = q3 dan δ(q3, 1) = q4 à (q3, q4) distinguishable maka
(q0, q3) adalah distinguishable.
· Untuk pasangan (q1, q2)
δ(q1, 0) = q2 dan δ(q2, 0) = q1 à belum teridentifikasi dan q1, q2 ÏF
δ(q1, 1) = q4 dan δ(q2, 1) = q4 à q4 Î F, maka (q1,q2) mungkin
indistinguishable.
· Untuk pasangan (q1, q3)
δ(q1, 0) = q2 dan δ(q3, 0) = q2 à belum teridentifikasi dan q2 ÏF
δ(q1, 1) = q4 dan δ(q3, 1) = q4 à q4 Î F, maka (q1,q3) mungkin
indistinguishable.
· Untuk pasangan (q2, q3)
δ(q2, 0) = q1 dan δ(q3, 0) = q2 à belum teridentifikasi dan q1, q2 ÏF
δ(q2, 1) = q4 dan δ(q3, 1) = q4 à q4 Î F, maka (q1,q2) mungkin
indistinguishable.
Karena berdasarkan relasi-relasi yang ada, tidak dapat dibuktikan (q1, q2), (q1, q3) dan (q2, q3) distinguishable, sehingga disimpulkan pasangan-pasangan state tersebut indistinguishable.
4. Karena q1 indistinguishable dengan q2, q2 indistinguishable dengan q3, maka dapat disimpulkan q1, q2, q3 saling indistinguishable dan dapat dijadikan satu state.
Berdasarkan langkah 1 s/d 4, dapat digambarkan DFA yang sudah direduksi statenya sebagai berikut.
Kedua mesin sebelum dan sesudah direduksi akan tetap menerima bahasa yang sama.
DAFTAR PUSTAKA
DAPATKAN MAKALAH FINITE STATE AUTOMATA.DOC
Demikianlah Artikel Makalah Finite State Automata
Sekian Posting Makalah Finite State Automata, mudah-mudahan bisa memberi manfaat untuk anda semua.
Belum ada tanggapan untuk "Makalah Finite State Automata"
Posting Komentar