Blog Teori Bahasa Dan Otomata tentang Ekuivalensi NFA Ke DFA || Muhammad Tegar Wiratama Pohan_ 202131169

 

EKUIVALENSI NON-DETERMINISTIC FINITE STATE AUTOMATA (NFA) KE DETERMINISTIC FINITE STATE AUTOMATA(DFA)

Ekuivalen artinya sama, pada bahasan materi ini artinya dapat menerima string yang sama baik itu menggunakan mesin Non-Deterministc Finite Automata (NFA) maupun Deterministc Finite Automata (DFA).

Sebuah mesin Non-Deterministc Finite Automata (NFA) dapat dibuat menjadi mesin Deterministic Finite Automata(DFA) yang dapat menerima string yang sama. Ada beberapa tahap yang dapat ditempuh untuk melakukan ekuivalensi Non-Deterministc Finite Automata (NFA) ke Deterministc Finite Automata (DFA) :

1.     Buat tabel transisi dari Non-Deterministc Finite Automata (NFA)

2.     Telusuri state berikutnya dengan memanfaatkan tabel transisi ditambah dengan state { }

3.     Tentukan finish baru jika ada, dengan melihat seluruh state yang mengandung finish awal.

Contoh kasus diberikan gambar Non-Deterministc Finite Automata (NFA) berikut : Diketahui :


Q = {qo,q1}

Σ = {0,1} S = q0

F = {q1}

Ditanyakan :

Buatlah Deterministic Finite Automata yang ekuivalen dengan Non-Deterministic Finite Automata diatas.

Jawab :

1.    
Buat tabel transisi dari Non-Deterministc Finite Automata (NFA)

δ

0

1

q0

{q0,q1}

{q1}

q1

{ }

{ }


 

2.     Telusuri state berikutnya dengan memanfaatkan tabel transisi ditambah dengan state { }

   

δ

0

1

q0

{q0,q1}

{q1}

q1

{ }

{ }

{ q0,q1}

{q0,q1}

{q1}

{ }

{ }

{ }

 

3.     Tentukan finish baru jika ada, dengan melihat seluruh state yang mengandung finish awal.

                

δ

0

1

q0

{q0,q1}

{q1}

q1

{ }

{ }

{ q0,q1}

{q0,q1}

{q1}

{ }

{ }

{ }

         

4.     Gambar Deterministic Finite Automata :



Sebagai contoh, akan dibuat Deterministic Finite Automata dari Non-Deterministic Finite Automata sebagai berikut :

diketahui Ʃ : {0,1}

Buatlah tabel transisinya

Kedua kita buat tupel dari tabel tersebut agar lebih detail

δ  = {q0 , q1}

Ʃ = {0 , 1}

s =  q0

f =  q1

Lalu kita mulai membuat DFA nya

Dimulai dari state awal q0

·                State {q0} bila memperoleh input 0 menjadi state {q0, q1}.

·                State {q0} bila memperoleh input 1 menjadi state {q1}.

Ekuivalensi Non-Deterministic Automata (NFA)  ke Deterministic Finite Automata (DFA)

·                State {q1} memperoleh input 0 menjadi state ∅

·                State {q1} bila memperoleh input 1 menjadi state {q0, q1}.

Pada state {q0,q1} awalnya belum mempunyai busur dan pada DFA,sebuah state harus mempunyai busur sebanyak himpunan inputnya,karena itu kita tentukan terlebih dahulu arah busurnya dan busurnya ada 2.

δ({q0,q1},0)  = {q0,0} ε {q1,0}

          = {q0,q1} ε Ø

          = {q0,q1}

δ({q0,q1},1) = {q0,1} ε {q1,1}

          = {q1} ε {q0,q1}

          = {q0,q1}

Jadi arah busur pada state {q0,q1} mengarah ke state itu sendiri.

Kemudian khusus pada state himpunan kosong (Ø) hanya menerima inputan dari statenya sendiri,jadi busur pada himpunan kosong mengarah ke state himpunan kosong.

Ekuivalensi Non-Deterministic Automata (NFA)  ke Deterministic Finite Automata (DFA)

Terakhir untuk menentukan final state pada DFA ini adalah dengan melihat NFA yang ekuivalen dengan DFA ini yaitu soal awal,

Kita ketahui Bahwa final state adalah q1,jadi pada DFA,final statenya adalah semua state yang ada hubungannya dengan q1 yaitu {q0,q1} dan {q1}

Ekuivalensi Non-Deterministic Automata (NFA)  ke Deterministic Finite Automata (DFA).

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