Blog Teori Bahasa Dan Otomata tentang Derivasi Kalimat dan Penentuan Bahasa || Muhammad Tegar Wiratama Pohan_ 202131169

 Pengertian Ekuivalensi Antar Deterministic Finite Automata


Sasaran kita disini 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: 

•Distinguishable yang berarti dapat dibedakan.
•Indistinguishable yang berarti tidak dapat dibedakan.

Reduksi dilakukan untuk mengurangi jumlah state tanpa mengurangi kemampuan untuk menerima suatu Bahasa seperti semula (efisiensi). State pada FSA dapat direduk siapa bila terdapat useless state. Hasil dari FSA yang direduksi merupakan ekivalensi dari FSA semula.


Lakukan reduksi state pada DFA diatas?

Jawabannya sebagai berikut :

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 sedangkan q0, q1, q2, q3 ÏF   sehingga  pasangan
 Pasangan State :
 (q0,q1)
 (q0,q2)
 (q0,q3)
 (q0,q4)
 (q1,q2)
 (q1,q3)
 (q1,q4)   
 (q2,q3)
 (q2,q4)
 (q3,q4)

Reduksi Jumlah State Pada FSA –Step

Pasangan State =
 (q0,q1)
 (q0,q2)
 (q0,q3)
 (q0,q4) → Distinguisable
 (q1,q2)
 (q1,q3)
 (q1,q4) → Distinguisable
 (q2,q3)
 (q2,q4) → Distinguisable
 (q3,q4) → Distinguisable


Cari Status Pasangan lainnya, dengan memperhatikan inputan yang tersedia yaitu 0 dan 1
■Pasangan (q0,q1)
  ➢ δ(q0, 0) = q1dan δ(q1, 0) = q2 ➔ (q1 ,q2) belum terdefinisi
  ➢ δ(q0,1) = q3 dan δ(q1, 1) = q4 ➔ (q3 ,q4) Distinguisable
Maka (q0, q1) adalah Distinguishable


Cari Status Pasangan lainnya, dengan memperhatikan inputan yang tersedia yaitu 0 dan 1
■Pasangan (q0,q2)
  ➢ δ(q0, 0) = q1dan δ(q2, 0) = q1 ➔ (q1 ,q1) belum terdefinisi
  ➢ δ(q0, 1) = q3 dan δ(q2, 1) = q4 ➔ (q3 ,q4) Distinguisable
Maka (q0, q2) adalah Distinguishable


Cari Status Pasangan lainnya, dengan memperhatikan inputan yang tersedia yaitu 0 dan 1
■Pasangan (q0,q3)
  ➢ δ(q0, 0) = q1 dan δ(q3, 0) = q2 ➔ (q1 ,q2) belum terdefinisi
  ➢ δ(q0, 1) = q3 dan δ(q3, 1) = q4 ➔ (q3 ,q4) Distinguisable
Maka (q0, q3) adalah Distinguishable


Cari Status Pasangan lainnya, dengan memperhatikan inputan yang tersedia yaitu 0 dan 1
■Pasangan (q1,q2)
  ➢ δ(q1,0) = q2 dan δ(q2, 0) = q1 ➔ (q2 ,q1) belum terdefinisi
  ➢ δ(q1, 1) = q4 dan δ(q2,1) = q4 ➔ (q4 ,q4) belum terdefinisi
Maka (q1, q2) adalah belum terdefinisi


Cari Status Pasangan lainnya, dengan memperhatikan inputan yang tersedia yaitu 0 dan 1
■Pasangan (q1,q3)
  ➢ δ(q1, 0) = q2 dan δ(q3, 0) = q2 ➔ (q2 ,q2) belum terdefinisi
  ➢ δ(q1, 1) = q4 dan δ(q3, 1) = q4 ➔ (q4 ,q4) belum terdefinisi
Maka (q1, q3) adalah belum terdefinisi


Cari Status Pasangan lainnya, dengan memperhatikan inputan yang tersedia yaitu 0 dan 1
■Pasangan (q2,q3)
  ➢ δ(q2,0) = q1 dan δ(q3, 0) = q2 ➔ (q1 ,q2) belum terdefinisi
  ➢ δ(q2, 1) = q4 dan δ(q3, 1) = q4 ➔ (q4 ,q4) belum terdefinisi
Maka (q2, q3) adalah belum terdefinisi


Pasangan State :
(q0,q1) → Distinguishable
(q0,q2) → Distinguishable
(q0,q3) → Distinguishable
(q0,q4) → Distinguisable
(q1,q2) → belum terdefinisi
(q1,q3) → belum terdefinisi
(q1,q4) → Distinguisable
(q2,q3) → belum terdefinisi
(q2,q4) → Distinguisable
(q3,q4) → Distinguisable


Setelah semua pasangan state telah dipasangkan dengan setiap input yang ada maka terdapat state-state yang Distinguishable yaitu :
(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


Pasangan State :
(q0,q1) → Distinguishable
(q0,q2) → Distinguishable
(q0,q3) → Distinguishable
(q0,q4) → Distinguisable
(q1,q2) → indistinguishable
(q1,q3) → indistinguishable
(q1,q4) → Distinguisable
(q2,q3) → indistinguishable
(q2,q4) → Distinguisable
(q3,q4) → Distinguisable


Karena q1 indistinguishable dengan (q2,q1) indistinguishable dengan (q3,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:

 



Komentar

Posting Komentar

Postingan populer dari blog ini

Materi Minterm dan Maxterm

Gambar
  MEMAHAMI FUNGSI BOOLEAN, BENTUK KANONIK DAN BENTUK BAKU PADA SISTEM DIGITAL   PENGERTIAN Bentuk Kanonik merupakan Fungsi Boolean yang diekspresikan dalam bentuk SOP (Sum of Product) atau POS (Product of Sum) dengan minterm/maxterm. Kanonik memiliki literal yang lengkap. Sedangkan bentuk baku merupakan Fungsi Boolean yang diekspresikan dalam bentuk SOP atau POS dengan minterm atau maxterm mempunyai literal yang tidak lengkap.  Untuk dalam memahami secara lengkap SOP (Sum of Product) diistilahkan dengan jumlah dari hasil perkalian. POS (Product of Sum) diistilahkan dengan perkalian dari hasil penjumlahan. Untuk dapat memperoleh ekspresi Boolean yang harus diperhatikan hanyalah “ output  = 1”.  Suku-suku bentuk SOP disebut  minterm . sedangkan Untuk mendapatkan mendapatkan bentuk POS ( maxterm)  diperhatikan hanyalah “keluaran bernilai 0”. 1.1         TABEL BOOLEAN BENTUK IKONIK DAN BAKU Tabel kebenaran ad...
Baca selengkapnya

Teknik Digital

Gambar
Apa itu Teknik Digital ?   Menurut kamus besar indonesia  :  DIGITAL adalah semua yang berhubungan dengan angka-angka untuk sistem perhitungan atau penomoran. DIGITAL   adalah hasil teknologi yang mengubah sinyal menjadi kombinasi urutan bilangan yang mempunyai harga 0 dan 1 (bilangan biner) yang terdapat dalam sebuah sistem elektronik tertentu untuk proses informasi yang mudah, cepat dan akurat. Sinyal tersebut disebut sebuah bit. Konsep digital memberikan gambaran pemahaman suatu keadaan yang saling berlawanan. Pada contoh lampu, bila saklar ditekan pada tombol on, lampu akan menyala dan ruangan akan tampak terang. Sebaliknya bila saklar ditekan pada tombol off, maka lampu akan mati dan ruangan menjadi gelap. Di dunia ini banyak kondisi yang hanya mempuanyai dua kondisi seperti ON dan OFF seperti jenis kelamin yaitu Laki-laki dan Perempuan, kondisi katub terbuka dan tertutup, waktu siang dan malam, status pegawai aktif dan tidak aktif, suasana hati sedih dan bahagi...
Baca selengkapnya

Multiplexer & Dimultiplexer

Gambar
  MULTIPLEXER &  DIMULTIPLEXER Nama : Muhammad Tegar (202131169) & Azmi Azis (202131154) Sebuah multiplexer adalah rangkaian logika yang menerima beberapa input data digital dan menyeleksi salah satu dari input tersebut pada saat tertentu, untuk dikeluarkan pada sisi output. Seleksi data-data input juga dilakukan oleh selector line, yang juga merupakan input dari multiplexer tersebut. Blok diagram sebuah multiplexer ditunjukkan pada gambar berikut. Jumlah data input maksimum pada multiplexer ditunjukkan pada tabel berikut. Rangkaian multiplexer ditunjukkan pada gambar berikut. Atau dengan kata lain multiplexer yaitu rangkaian elektronika yang dapat dipilih untuk meneruskan data/sinyal kedalam outputnya. Sebagai contoh adalah gambar berikut. Gambar diatas bisa diumpamakan sebuah saklar yang akan memin...
Baca selengkapnya