ILMU KOMPUTER (FAKHRI_UNSIKA): FINITE STATE AUTOMATA

Finite State Automata

Non Finite State Automata

BAHASAN

1. Penerapan FSA

2. DFA

3. NDFA/NFA

4. Ekuivalen antar DFA

5. Reduksi Jumlah State pada FSA

Penerapan (FSA)

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).

Finite State Automata

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

Finite State Automata

Contoh 1: Seorang petani dengan seekor serigala, kambing dan seikat rumput beradapadasuatusisi 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,makakambingakan dimakanserigala. Begitu pula jika kambing ditinggalkan dengan rumput, maka rumput akandimakanoleh kambing. Mungkinkah ditemukan suatu care untuk melintasi sungai tanpa menyebabkan kambing atau rumput dimakan.

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}

Finite State Automata

Contoh2:

Pengecek Pariti Ganjil

FSA dari bentuk diatas

• Lingkaran menyatakan state/kedudukan

• Label pada lingkaran adalah nama state tersebut

• Busur menyatakan transisi yaitu perpindahan kedudukan/state.

• Label pada busur adalah simbol input.

• Lingkaran didahului sebuah busur tanpa label menyatakan state awal

• Lingkaran ganda menyatakan state akhir/final

Bila mesin mendapatkan input

Input: 1101

Urutan state yang terjadi:

Genap—1–ganjil –1— genap—0—genap—1— ganjil, (berakhir pada ganjil) sehingga ‘1101’diterima oleh mesin.

Input: 101

Urutan state yang terjadi: Genap—1—ganjil—0— ganjil—1—genap, (berakhir pada genap) sehingga ‘101’ ditolak oleh mesin.

Tupel: M =(Q, ∑, δ, S, F)

Q = {genap, ganjil}

Σ = {0,1}

S = genap

F = {ganjil}

FSA (Finite State Automata)

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.

2. Nondeterministic Finite Automata (NDFA) / NFA
Artinya: Dari suatu state bisa terdapat 0,1 atau lebih busur keluar (transisi) berlabel simbol input yang sama

PENERAPAN KONSEP

FINITE STATE AUTOMATA

(FSA)

PADA MESIN PEMBUAT MINUMAN KOPI OTOMATIS

Jurusan Ilmu Komputer FMIPA Universitas Lampung Jurusan Matematika FMIPA Universitas Lampung Abstract

This research discusses about a simulating application for automatic coffee machine which can do processes of making 7 types of choices of drinks; coffee, milk, chocolate, coffee milk, coffee brown, mocha, and chocolate milk automatically. In this application, the concept of Finite State Automata (FSA) was applied to recognize and to capture the pattern on the process for making coffee drinks. In this application, Finite State Automata (FSA) was applied to read input symbols given from the starting state to the final state in order to get the language recognized by the machine. Further, the process will be done accordance with the read language. Keywords: Coffee Machine, Finite State Automata (FSA), Language and Automata Theory.

1 Pendahuluan Perkembangan zaman yang semakin modern mengubah pola pikir manusia untuk berfikir lebih maju, menciptakan serta mengembangkan berbagai teknologi baru, dimana teknologi tersebut diciptakan untuk memudahkan kegiatan manusia. Mesin otomatis merupakan salah satu teknologi yang sengaja diciptakan untuk mengubah suatu kegiatan yang bersifat manual menuju otomatis dengan tujuan mempercepat proses kegiatan tersebut. Salah satu mesin otomatis yang mulai berkembang saat ini adalah mesin pembuat minuman kopi otomatis. Mesin pembuat minuman kopi otomatis muncul sebagai suatu terobosan baru untuk memudahkan serta mempercepat proses pembuatan minuman kopi dan variasinya. Dengan banyaknya variasi ataupun pilihan jenis minuman kopi yang diberikan, tentunya mesin pembuat minuman kopi otomatis ini harus dapat melakukan proses pembuatan minuman yang sesuai berdasarkan pilihan yang diberikan. Untuk mengatasi permasalahan dalam proses pembuatan minuman kopi secara otomatis, penerapan konsep Finite State Automata (FSA) pada suatu mesin pembuat minuman kopi otomatis merupakan pilihan yang tepat untuk memodelkan proses pembuatan minuman kopi secara 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. Aplikasi simulasi mesin pembuat minuman kopi otomatis ini dibangun dengan menggunakan tools Microsoft Visual Studio 2008. Pada aplikasi akan digunakan 8 bahan dasar pembuat minuman yaitu : gelas dengan tiga jenis ukuran yaitu small, medium dan large, air, gula, bubuk kopi, bubuk susu, dan bubuk coklat. Selanjutnya, dari bahan tersebut mesin dapat membuat 7 jenis produk minuman yaitu : kopi, susu, coklat, kopi susu, kopi coklat, kopi susu coklat dan susu coklat. Aplikasi ini juga dirancang hanya sebagai mesin yang dapat melakukan proses

Hal 95 dari 102

Melly, Wamiliana, Kurniawan: Penerapan Konsep Finite State Automata (FSA)Pada Mesin Pembuat Minuman Kopi Otomatis

pembuatan minuman kopi secara otomatis dan tidak melakukan proses transaksi penjualan, sehingga tidak membutuhkan input berupa uang koin maupun uang kertas. 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. Manfaat yang dapat diperoleh dari penelitian ini adalah memahami tentang penerapan konsep FSA pada mesin pembuat minuman kopi otomatis. Penerapan konsep FSA dapat menjadi salah satu alternatif untuk merancang suatu mesin pembuat minuman kopi otomatis serta menjadi bahan pertimbangan dan acuan yang positif dalam pengembangan aplikasi selanjutnya yang sejenis.

2 Metode Metode yang digunakan dalam pelaksanaan penelitian ini adalah formal methods. Formal methods atau metode formal, dalam ilmu komputer dan rekayasa perangkat lunak, adalah suatu pemodelan matematika, yang dapat digunakan untuk menjembatani (spesifikasi formal) pembuatan, pengembangan dan verifikasi perangkat keras dan piranti lunak, yang dapat digunakan dari perancangan awal sampai pengujian hasil [3].

2.1 Spesifikasi Formal (Formal Specification)

Spesifikasi formal atau formal specification adalah spesifikasi yang dinyatakan dalam bentuk bahasa yang didefinisikan secara formal untuk menggambarkan apa yang harus dilakukan perangkat lunak [2]. Pada penelitian ini teknik spesifikasi formal yang akan digunakan adalah berorientasi model yaitu dengan membuat suatu model perilaku sistem menggunakan obyek matematika seperti set dan urutan, yaitu diantaranya state charts dan automata model teoritis.

Keterangan : 0 a b c d e f g h i j k q l r m s n t o p

: kembali ke start state : pilih minuman kopi : pilih minuman susu : pilih minuman coklat : pilih minuman kopi susu : pilih minuman kopi coklat : pilih minuman mocca : pilih minuman susu coklat : gelas S : gelas M : gelas L : gula : tambah gula : kopi : tambah kopi : susu : tambah susu : coklat : tambah coklat : air : aduk (final state)

Gambar 1 Diagram transisi mesin pembuat minuman kopi otomatis

Hal 96 dari 102

Jurnal komputasi, Desember 2012, Vol 1, No. 1

Berdasarkan diagram transisi yang telah dibentuk maka dapat dikonstruksikan aturan produksi dari FSA aplikasi simulasi mesin pembuat minuman kopi otomatis yaitu :

Misal S0 = S, S1=A, S2=B, S3=C, S4=D, S5=E, S6=F, S7=G, S8=H, S9=I, S10=J, S11=K, S12=L, S13=M, S14= N, S15=O, S16=Final State. Maka : G = {VT, VN, S, P} VT = {a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, 0 } VN= {S, A, B, C, D, E, F, G, H, I, J, K, L, M, N,O} S=S P = {S→ aA | bB | cC | dD | eE | fF | gG | 0, A → hH | iI | jJ | S, B → hH | iI | jJ | S, C → hH | iI |jJ | S, D → hH | iI | jJ | S, E → hH | iI | jJ | S, F → hH | iI | jJ | S, G → hH | iI | jJ | S, H → kK | S, I → kK | S, J → kK | S, K→ qK | lL | mM | nN | S, L → rL | mM | nN| oO | S, M → sM | nN |oO | S, N → tN | oO | S , O → p | S } Diagram transisi tersebut menggambarkan spesifikasi proses yang terdapat pada mesin pembuat minuman kopi otomatis yang menerapkan konsep FSA. Mesin akan mengikuti pola alur dari proses pembuatan minuman sesuai dengan pilihan jenis minuman. Sehingga, dimungkinkan tidak terjadi kesalahan dalam proses pembuatan minuman yang sesuai dengan jenis pilihan minumannya. FSA digunakan untuk membaca simbol masukan yang diberikan dari start state sampai final state sehingga diperoleh suatu bahasa yang dikenali oleh mesin. Selanjutnya dilakukan proses pembuatan minuman sesuai dengan bahasa yang dibaca.

2.2 Implementasi Setelah melakukan spesifikasi maka tahap selanjutnya adalah implementasi. Pada aplikasi simulasi mesin pembuat minuman kopi otomatis diterapkan konsep FSA untuk pemodelan proses pembuatan minuman kopi secara otomatis. Spesifikasi formal yang telah ditentukan sebelumnya kemudian diimplementasikan kedalam suatu kode program yang menerapkan konsep FSA didalam kode program tersebut. Secara umum proses tersebut tergambar pada potongan bagan alur (Flowchart) berikut ini:

Hal 97 dari 102

Melly, Wamiliana, Kurniawan: Penerapan Konsep Finite State Automata (FSA)Pada Mesin Pembuat Minuman Kopi Otomatis Mulai

STOK BAHAN HABIS

If bahan >= batas minumum stok bahan

Buka group box pilihan jenis minuman

Pilih jenis minuman

Baca simbol masukkan pilihan jenis minuman

If gelasS>0 or If gelasM >0 or If gelasL>0 or

STOK GELAS HABIS

STOK BAHAN EXTRA HABIS

Y Buka group box ukuran gelas

Pilih jenis ukuran gelas T Baca simbol masukkan pilihan ukuran gelas dan air

If bahan tambahan >= ukuran min stok tambahan

Y Buka group box bahan extra

If pilih extra

Y input banyak extra max 3x Baca simbol masukkan jenis dan banyaknya bahan extra yang ditambah

If Pilih proses minuman

Y Baca keseluruhan simbol masukkan Parsing grammar yg terbentuk dan membuat minuman

TERIMAKASIH . SELAMAT MENIKMATI MINUMAN ANDA.

Selesai

Gambar 2 Flowchart aplikasi mesin pembuat minuman kopi dengan konsep FSA Hal 98 dari 102

Jurnal komputasi, Desember 2012, Vol 1, No. 1

2.3 Verifikasi Formal (Formal Verification)

Verifikasi Formal yaitu membuktikan bahwa suatu implementasi betul-betul mengimplementasikan apa yang dijabarkan dalam spesifikasinya. Pada penelitian ini teknik verifikasi formal yang digunakan adalah model checking. Dalam model checking ingin diuji apakah desain memang seperti yang diharapkan. Membuat suatu model abstrak dari desain, kemudian dapat membuktikan properties dari desain tersebut dengan menguji fungsi-fungsi yang terdapat pada software tersebut.

3 Pembahasan

Aplikasi Simulasi Mesin Pembuat Minuman Kopi Otomatis merupakan aplikasi simulasi suatu mesin yang dapat melakukan proses pembuatan minuman kopi dan variasinya secara otomatis dimana dalam penyelesaian prosesnya digunakan konsep Finite State Automata (FSA). Konsep FSA digunakan untuk menangkap dan mengenal pola dalam proses pembuatan minuman kopi pada mesin pembuat minuman kopi otomatis, dengan membaca input yang diberikan dan masuk ke dalam proses pengecekkan inputan tersebut sampai dengan state akhir kemudian akan melakukan proses sesuai dengan jalur input tersebut (Gambar 1). Gambar 3 merupakan tampilan utama dari Aplikasi Simulasi Mesin Pembuat Minuman Kopi Otomatis.

Gambar 3 Interface menu utama aplikasi

Metode pengujian yang digunakan adalah model checking. Dalam model checking ingin diuji apakah desain ini memang seperti yang yang diharapakan. Teknik pengujian yang digunakan adalah dengan membuat daftar dari kemungkinan kesalahan yang terjadi pada aplikasi dan selanjutnya mengikuti alur pengujian sesuai dengan daftar. Tabel 1 Daftar Pengujian Aplikasi No 1

Pengujian Fungsi aplikasi

Detail a. Kesesuaian input pilihan dengan output b. Kesesuain output grammar dengan pilihan yang diberikan c. Proses pengurangan stok d. Proses pengisian stok

Hal 99 dari 102

Melly, Wamiliana, Kurniawan: Penerapan Konsep Finite State Automata (FSA)Pada Mesin Pembuat Minuman Kopi Otomatis

Tabel 1 Daftar Pengujian Aplikasi (lanjutan) 2

Interface aplikasi

a. Apakah tombol pilihan ekstra yang diberikan sesuai dengan pilihan jenis minuman yang dipilih b. Men-disable pilihan jenis minuman, jenis ukuran gelas dan ekstra bubuk yang kurang dari stok minimum c. Pemberitahuan informasi (respon aplikasi) d. Manipulasi tombol

Hasil dari pengujian yang dilakukan berdasarkan daftar pengujian tersebut ditunjukkan pada Tabel 2 di bawah ini: Tabel 2 Daftar Hasil Pengujian Aplikasi No 1

Pengujian Fungsi aplikasi

a. b. c. d.

2 Interface aplikasi

Detail Kesesuaian input pilihan dengan output Kesesuaian output grammar dengan pilihan yang diberikan Proses pengurangan stok Proses pengisian stok

Keterangan Baik Baik Baik Baik Baik

Baik

Baik Baik

4 Kesimpulan Berdasarkan hasil penelitian dan analisis dari penerapan Finite State Automata (FSA) pada mesin pembuat minuman kopi otomatis, maka dapat disimpulkan bahwa: Finite State Automata (FSA) dapat menjadi salah satu alternatif untuk merancang suatu mesin pembuat minuman kopi otomatis yang flexible dalam hal mengenal dan menangkap pola dalam proses pembuatan minuman kopi dan variasinya. Konsep FSA pada mesin pembuat minuman kopi otomatis diterapkan dengan cara FSA membaca setiap simbol masukan yang diberikan menjadi suatu bahasa yang dikenali oleh FSA. Mesin selanjutnya akan melakukan proses pembuatan minuman sesuai dengan bahasa yang telah dibaca oleh FSA. Adapun saran yang dapat diberikan untuk pengembangan penelitian ini lebih lanjut yaitu dengan memberikan fitur proses transaksi penjualan secara otomatis, sehingga mesin tidak hanya dapat melakukan proses pembuatan minuman tetapi juga dapat melakukan proses transaksi penjualan secara otomatis.

DETERMINISTIC FINITE AUTOMATA (DFA)

Deterministic Finite Automata

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)

Deterministic Finite Automata

Penelusuran/Tracking:

Telusurilah, apakah kalimat-kalimatberikut 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.

Input: abb

Maka Tracking:

δ(q0,abb) = δ(q0,bb) =

δ(q1,b) = q2
Karena q2 termasuk dalam state akhir, maka “abb” berada dalam L(M)

Input: baba
Maka:
δ(q0,baba) = δ(q1, aba)
= δ(q1,ba) = δ(q2,a) = q1

Karena q1, tidak termasuk state akhir, maka “baba”tidak berada dalam L(M)

Penjelasan dan Contoh Program DFA

(Deterministic Finite Automaton) dengan Bahasa C

Written by: guest (嘉男)

Updated on: Oktober 19, 2018

Deterministic Finite Automaton

Pengertian DFA (Deterministic Finite Automaton)

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 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 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.

NONDETERMINISTIC FINITE AUTOMATA (NFA)

Non Deterministic Finite Automata

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)

Sebuah kalimat di terima NFA jika:

Salah satu tracking-nya berakhir di state AKHIR, atau himpunan state setelah membaca string tersebut mengandung state AKHIR

Telusurilah, apakah kalimat-kalimat berikut diterima NFA di atas : ab, abc, aabc, aabb

Jawab:

δ(q0 ,ab) ⇒ δ(q0,b) ∪ δ(q1 ,b) ⇒ {q0, q2} ∪ {q1 } = {q0 , q1 , q2} Himpunan state TIDAK mengandung state AKHIR ⇒ kalimat ab tidak diterima

δ(q0 ,abc) ⇒ δ(q0 ,bc) ∪ δ(q1 ,bc) ⇒ { δ(q0 ,c) ∪ δ(q2 ,c)}∪δ(q1 , c) {{ q0 , q3 }∪{ q2 }}∪{ q1 } = {q0 , q1 , q2 ,q3 }

Himpunan state TIDAK mengandung state AKHIR ⇒ kalimat abc tidak diterima.

Sebuah NFA menerima string, jika:
Kamputasi pada NFA menerima string
Komputasi adalah : Seluruh inputan dimasukkan dan automata dimulai dari state awal menuju ke state akhir

Ekuivalensi Antar Deterministic Finite Automata

DuaDFA M1 danM2 dinyatakanekivalenapabilaL(M1) = L(M2)

Setelah kita mempelajari tentang DFA, pada kali ini kita akan mempelajari ekivalensi antar DFA. Bersama saya Sola, mari perhatikan materi ini:

Sasaran : Mengurangi jumlah state dari FSA, dengan tidak mengurangi kemampuannya semula untuk menerima sebuah bahasa.

Istilah yang digunakan :

Distinguisable = dapat dibedakan

Indistinguisable = tidak dapat dibedakan

Reduksi Jumlah State pada FSA :

Reduksi dilakukan untuk mengurangi jumlah state tanpa mengurangi kemampuan untuk menerima suatu bahasa seperti semula.

State pada FSA dapat direduksi apabila terdapat useless state.

Hasil FSA yang direduksi merupakan ekivalensi dari FSA semula.

Keterangan : Useless state adalah state yang tidak menerima inputan dari manapun tetapi mengeluarkan output.

(q0,q1)

q0,0 -> q1 & q1,0 -> q1 => q1,q1 -> indistinguisable, sehingga dapat direduksi.

Contoh Soal 1 :

Penyelesaian :

Didapat State yang tidak useless : q0, q1, q2, q3, q4

q0, q1 -> distinguisable

q0, q2 -> distinguisable

q0, q3 -> distinguisable

q0, q4 -> distinguisable

q1, q2 -> indistinguisable

q1, q3 -> indistinguisable

q1, q4 -> distinguisable

q2, q3 -> indistinguisable

q2, q4 -> distinguisable

q3, q4 -> distinguisable

Pembuktian :

(q0, q1)

q0, 0 -> q1 & q1, 0 -> q2 =>q1, q2

q0, 1 -> q3 & q1, 1 -> q4 => q3, q4 = distinguisable

(q0, q2)

q0, 0 -> q1 & q2, 0 -> q1 =>q1, q1

q0, 1 -> q3 & q2, 1 -> q4 => q3, q4 = distinguisable

(q0, q3)

q0, 0 -> q1 & q3, 0 -> q1 =>q1, q1

q0, 1 -> q3 & q3, 1 -> q4 => q3, q4 = distinguisable

(q1, q3)

q1, 0 -> q2 & q3, 0 -> q2 =>q2, q2

q1, 1 -> q4 & q3, 1 -> q4 => q4, q4 = indistinguisable

(q1, q2)

q1, 0 -> q2 & q2, 0 -> q1 =>q1, q2

q1, 1 -> q4 & q2, 1 -> q4 => q4, q4 = indistinguisable

(q2, q3)

q2, 0 -> q1 & q3, 0 -> q2 =>q1, q2

q2, 1 -> q4 & q3, 1 -> q4 => q4, q4 = indistinguisable

jadi dapat direduksi menjadi :

Contoh soal 2 :

Lakukan reduksi terhadap state berikut:

Penyelesaian:

Maka state yang tidak useless didapat : q0, q1, q2, q3, q4

q0, q1 -> distinguisable

q0, q2 -> distinguisable

q0, q3 -> distinguisable

q0, q4 -> distinguisable

q1, q2 -> indistinguisable

q1, q3 -> distinguisable

q1, q4 -> distinguisable

q2, q3 -> distinguisable

q2, q4 -> distinguisable

q3, q4 -> indistinguisable

Pembuktian :

(q0, q1)

q0, 0 -> q1 & q1, 0 -> q2 =>q1, q2

q0, 1 -> q2 & q1, 1 -> q3 => q2, q3 = distinguisable

(q0, q2)

q0, 0 -> q1 & q2, 0 -> q2 =>q1, q2

q0, 1 -> q2 & q2, 1 -> q4 => q2, q4 = distinguisable

(q1, q2)

q1, 0 -> q2 & q2, 0 -> q2 =>q2, q2

q1, 1 -> q3 & q2, 1 -> q4 => q3, q4 = indistinguisable

sehingga dapat direduksi menjadi :

Reduksi Jumlah State Pada FSA

• Reduksi dilakukan untuk mengurangi jumlah state tanpa mengurangi kemampuan untuk menerima suatu bahasa seperti semula (efisiensi)

• Statepada FSA dapat direduksi apabila terdapat useless state

• Hasil dari FSA yang direduksi merupakan ekivalensi dari FSA semula

Reduksi Jumlah State Pada FSA

Pasangan Statedapat dikelompokkan berdasarkan:

• Distinguishable State (dapat dibedakan) Dua state p dan q dari suatu DFA dikatakan indistinguishableapabila:

δ(q,w) ∈F dan δ(p,w) ∈F atau δ(q,w) ∉ F dan δ(p,w) ∉ F untuk semua w ∈S*

• Indistinguishable State ( tidak dapat dibedakan) Dua state p dan q dari suatu DFA dikatakan distinguishablejika 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

• 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 state yang distinguishable merupakanstate-stateindistinguishable.

• Beberapa state yang indistinguishable dapat digabungkan menjadi satu state.

• Sesuaikan transisi dari state-state gabungan tersebut.

Reduksi Jumlah State Pada FSA – Step

• 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.

Reduksi Jumlah State Pada FSA – Step

• 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 re lasi-relasi yang ada, tidak dapat dibuktikan (q1, q2), (q1, q3) dan (q2, q3) distinguishable, sehingga disimpulkan pasanganpasangan 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:

Reduksi Jumlah State pada FSA

mengurangi jumlah state dari suatu FSA dengan tidak mengurangi kemampuan menerima suatu bahasa

Distinguishable = dapat di bedakan

Indistinguishable = tidak dapat dibedakan

state p dan q Indistinguishable jika :

δ (q,w) ∈ F sedang δ (p,w) ∈ F

atau

δ (q,w) ∉ F sedang δ (p,w) ∉ F

untuk semua w ∈ ∑*

state p dan q Distinguishable jika :

δ (q,w) ∈ F sedang δ (p,w) ∉ F

"jika p dan q Indistinguishable, dan jika q dan r juga Indistinguishable maka p dan r juga Indistinguishable dan ketiga state tersebut Indistinguishable"