EKUIVALENSI ANTARA DFA

EKUIVALENSI ANTARA NFA KE DFA


"Assalamualaikum wr.wb Selamat Pagi,Siang,Sore atau malam brothers semua,kali ini saya akan membahas tentang Materi Grammar dan Bahasa pada matakuliah Teori bahasa Otomata. so check this out brothers!!"


Ekuivalensi NFA ke DFA

  Dari sebuah mesin Non-deterministic Finite Automata dapat dibuat mesin Deterministic Finite Automata-nya yang ekuivalen.Ekuivalen disini artinya menerima bahasa yang sama .Meskipun yang satu adalah Non-deterministic dan yang satunya Deterministic namun keduanya menerima bahasa yang sama.  

Sasaran : mengurangi Jumlah State dari FSA dengan tidak mengurangi kemampuannya                   untuk menerima suatu bahasa.


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 dari FSA yang direduksi merupakan ekuivalensi dari FSA semula
*Useless : tidak memberi/menerima inputan siapa-siapa tapi punya output.

*Key*
apabila dari proses didapat hasil berikut,maka:
  • Dist + Dist = Indist
  • Indist + Dist = DIst
  • State Final Ketemu State FInal = Indist

Contoh Soal & jawaban

 


Komentar

Posting Komentar

Postingan populer dari blog ini

HIRARKI CHOMSKY

Gambar
HIRARKI CHOMSKY "Assalamualaikum wr.wb Selamat Pagi,Siang,Sore atau malam brothers semua,kali ini saya akan membahas tentang Materi Grammar dan Bahasa pada matakuliah Teori bahasa Otomata. so check this out brothers!!"  Sejarah Hirarki Chomsky Pada tahun 1959,seorang ahli bernama Noam Chomsky melakukan penggolongan tingkatan bahasa menjadi empat,yang disebut dengan hirarki chomsky. Penggolongan tersebut bisa diketahui melalui tabel berikut.... Hirarki Chomsky Dalam hirarki Chomsky a da 4(empat) kelas pengelompokan suatu bahasa, yaitu: 1.       Reguler (Level/Tipe 3) Mesin Automata : Finate State Automata. DFA dan NFA Aturan:- Simbol sebelah kiri harus berupa simbol variabel. -     Simbol sebelah kanan maksimal hanya memiliki simbol variabel dan bila ada terletak di paling kanan 2.       Bebas konteks (Level/Tipe 2) Mesin Automata : Push Down Automata Aturan:- Simb...
Baca selengkapnya

LKMM Pra-TD Teknik Informatika STT PLN JAKARTA

        Materi LKMM Pra TD 2K16 "Dua kata yang me mbangkitkan semangat juang kita, dua kata yang membuat para tikus -tikus berdasi lari ketakutan, dua kata yang dapat membuat perubahan besar terhadap negeri ini...  Hidup Mahasiswa!!! "          "Mahasisw a d iambil dari 2 kata yaitu Maha & Siswa yang memiliki arti sebagai kumpulan Manusi a yang memiliki jiwa sosial,serta Intelektual tinggi,dan sikap dewasa.Mahasiswa sendiri mem iliki peran penting ,yaitu Menjadi " Agent Of Ch ange" ata u menjadi generasi perubah. Generasi perubah disini diartikan sebagai calon emas penerus bangsa kelak. Mahasiswa sendiri mem iliki p eran diantara lain adalah sebagai garda terdepan rakyat.serta menjadi penyambung lidah rakyat yan g ter d z alimi oleh kaum el it yang mementingkan kepentingan pribadi tanpa memperdulikan nasi b rakyat." Oke cukup yaa pembaca untuk int ronya,se belum kita mas uk dalam Mater i, sudahkah se...
Baca selengkapnya