Ekuivalensi Antar Deterministic Finite Automata

 Ekuivalensi Antar Deterministic Finite Automata


A. Pengertian 

     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. istilah baru yang perlu diketahui :
1. Distinguishable, yang berarti dapat dibedakan
2. Indistinguishable, yang berarti tidak dapat dibedakan

B. 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 State dapat dikelompokkan berdasarkan :

1. Distinguishable State
    Dua state p dan q dari suatu DFA dikatakan indistinguishable apabila:
    • δ(q,w) anggota F dan δ(p,w) anggota F atau δ(q,w) ∉ F dan δ(p,w) ∉ F
    • untuk semua w anggota S* 
2. Indistinguishable State
    Dua state p dan q dari suatu DFA dikatakan distinguishable jika ada string w anggota S* hingga:
    δ(q,w) anggota F dan δ(p,w) ∉ F

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




    

               

Komentar

Posting Komentar

Postingan populer dari blog ini

Finite State Automata

Gambar
 Finite State Automata A. Pengertian       FSA (Finite State Automata) adalah alat atau tool yang berguna dalam merancang lexical analyzer,          yaitu bagian dari kompilator yang mengelompokan karakter-karakter ke dalam sebuah token, yang          berupa unit terkecil seperti nama, variabel, dan keyword. FSA dipakai untuk penganalisa leksikal dan     dipakai juga dalam text editor, pemrosesan teks, dan program file-searching B. Contoh Implementasi           Keterangan :      1. Mesin ini memiliki 6 state : (q0,q1,q2,q3,q4,q5).       2. State awal q0      3. Sedangkan q3 dan q4 adalah state akhir, dan       4. Simbol input adalah (a,d,u) C. Jenis FSA     1. DFA ( Deterministic)           Pada setiap input, hanya ada satu keadaan (st...
Baca selengkapnya

NFA Dengan E-Move

Gambar
 NFA Dengan E-Move 1. Pengertian       NFA dengan E-Move (transisi E-Move), diperbolehkan merubah State tanpa membaca input. Disebut dengan E-Move karena tidak bergantung pada 1 input saat melakukan transisi. E-Move Berada Pada Transisi State apabila Sebuah transisi mempunyai input / output / E-Move dan Suatu E-Move untuk state q1 ke q2 yang tehubung dapat berpindah tanpa menghasilkan inputan apapun pada transisi nya 2. E-Closure      E-Closure adalah himpunan state yang dapat di capai dari suatu state tanpa membaca input. Pada suatu state yang tidak memiliki E-Move, maka E-Closure nya adalah state itu sendiri 3. Contoh soal  Langkah - Langkah : 1. Buat table Transisi NFA E-Move dari diagram NFA semula 2. Cari E-Closure untuk setiap NFA 1. E-Closure (q0) = {q0, q1} 2. E-Closure (q1) = {q1} 3. E-Closure (q2) = {q2} 4. E-Closure (q3) = {q3}  3. Cari setiap fungsi transisi hasil perubahan dari...
Baca selengkapnya

Ekuivalensi NFA ke DFA

Gambar
 Ekuivalensi NFA ke DFA 1. Pengertian       Dari sebuah mesin Non-Deterministic Finite Automata dapat dibuat mesin Deterministic Finite              Automata-nya yang ekuivalen (bersesuaian). Ekuivalen di sini artinya mampu menerima bahasa yang      sama. Sebagai contoh, akan dibuat DFA dari DFA sebagai berikut : Dikertahui E = {0,1} Langkah - langkah : 1. Buat Table transisi dari diagram transisi tersebut 2. Buat diagram transisi untuk Finite State Automata dari tabel transisi di atas. 3. Table Transisi Ekuivalensi NFA ke DFA 4. Diagram Transisi Ekuivalensi NFA ke DFA
Baca selengkapnya