Blog Teori Bahasa Dan Otomata tentang NON-DETERMINISTIC FINITE STATE AUTOMATA (NFA) DENGAN ε-Move || Muhammad Tegar Wiratama Pohan_ 202131169

 

NON-DETERMINISTIC FINITE STATE AUTOMATA (NFA) DENGAN ε-Move
Suatu gambar Non-Deterministc Finite Automata (NFA) yang mengandung ε-Move ( ε dapat dianggap “empty” artinya dapat tidak dibaca inputannya atau diperbolehkan langsung menuju state berikutnya tanpa membaca inputan ε). Contoh gambar Non-Deterministic Finite Automata mengandung ε-Move :

Berdasarkan gambar diatas maka dapat di ambil kesimpulan :

v Dari q0 tanpa membaca input dapat langsung berpindah ke state q1

v Dari q2 tanpa membaca input dapat langsung berpindah ke state q3

Kegunaan transisi ε ini adalah memudahkan dalam mengkombinasikan Finite State Automata.


ε–closure merupakan himpunan state-state yang dapat dicapai dari suatu state tanpa membaca input. ε–closure sendiri dapat disingkat nantinya menjadi ε–cl. Contoh pada gambar berikut :


Berdasarkan gambar diatas, maka dapat di buat ε–closure nya sebagai berikut :

ü  ε–closure (q0) = {q0,q1}

ü  ε–closure (q1) = {q1}

ü  ε–closure (q2) = {q2,q3}

ü  ε–closure (q3) = {q3}

LATIHAN

Buatlah ε–closure dari gambar Non-Deterministic Finite Automata(NFA) berikut :

Dari suatu Non-Deterministic Finite Automata dengan ε – Move dapat dibuat ekuivalensinya menjadi Non-Deterministic Finite Automata tanpa ε – Move. Langkah-langkah melakukan ekuivalensi Non-Deterministic Finite Automata dengan ε – Move menjadi Non- Deterministic Finite Automata tanpa ε – Move :

1.     Buat tabel transisi Non-Deterministic Finite Automata yang mengandung ε – Move

2.     Tentukan ε- closure untuk setiap state

3. Carilah setiap fungsi transisi hasil perubahan Non-Deterministic Finite Automata ε –

Move ke Non-Deterministic Finite Automata tanpa ε – Move dengan menggunakan rumus :


Carilah setiap fungsi transisi hasil perubahan Non-Deterministic Finite Automata ε – Move ke Non-Deterministic Finite Automata tanpa ε – Move dengan menggunakan rumus :

4.     Buat table transisi baru dari hasil perolehan yang sudah dilakukan pada point(3)

5. Tentukan Final State dengan melihat state-state pada ε –closure yang menuju pada state finish semula

CONTOH

Buatlah NFA tanpa ε- Move yang ekuivalen dengan NFA dengan ε – Move berikut ini :

Langkah –langkah :

1.     Buat tabel transisi Non-Deterministic Finite Automata yang mengandung ε – Move

 

δ

0

1

q0

{ }

{ }

q1

q2

{ }

q2

{ }

{ }

q3

q3

q1

2.    Tentukan ε- closure untuk setiap state ε–closure (q0) = {q0,q1}

ε–closure (q1) = {q1} ε–closure (q2) = {q2,q3} ε–closure (q3) = {q3}

3.     Carilah setiap fungsi transisi hasil perubahan Non-Deterministic Finite Automata ε – Move ke Non-Deterministic Finite Automata tanpa ε – Move dengan menggunakan rumus :

δ' (q0,0)

=

ε – cl ( δ (ε – cl (q0),0))

ε – cl ( δ{q0,q1},0)

ε – cl ({q2})

{ q2,q3}

δ' (q0,1)

=

ε – cl ( δ (ε – cl (q0),1))

ε – cl ( δ{q0,q1},1)

ε – cl ({})

{ }

δ' (q1,0)

=

ε – cl ( δ (ε – cl (q1),0)) ε – cl ( δ{q1},0)

ε – cl ({q2})

{q2,q3}

δ' (q1,1)

=

ε – cl ( δ (ε – cl (q1),1)) ε – cl ( δ{q1},1)

ε – cl ({})

{ }

δ' (q2,0)

=

ε – cl ( δ (ε – cl (q2),0))

ε – cl ( δ{q2,q3},0)

ε – cl ({q3})

{q3}

δ' (q2,1)

=

ε – cl ( δ (ε – cl (q2),1))

ε – cl ( δ{q2,q3},1)

ε – cl ({q1})

{q1}

δ' (q3,0)

=

ε – cl ( δ (ε – cl (q3),0)) ε – cl ( δ{q3},0)

ε – cl ({q3})

{q3}


δ' (q3,1)

=

ε – cl ( δ (ε – cl (q3),1)) ε – cl ( δ{q3},1)

ε – cl ({q1})

{q1}



    4. Buat table transisi baru dari hasil perolehan yang sudah dilakukan pada point(3)

 

δ

0

1

q0

{q2,q3}

{ }

q1

{q2,q3}

{ }

q2

q3

q1

q3

q3

q1

1.     Tentukan Final State dengan melihat state-state pada ε –closure yang menuju pada state finish semula

Finis semula ada di q3, sehingga lihat state ε –closure yang menuju pada state q3 ε–closure (q0) = {q0,q1}

ε–closure (q1) = {q1} ε–closure (q2) = {q2,q3} ε–closure (q3) = {q3}

Berdasarkan ε–closure diatas maka dapat diperoleh state Finish lain selain q3 yaitu q2, sehingga final state sekarang ada 2 yaitu state q2 dan state q3.

Gambar Non-Deterministic Finite Automata tanpa ε-Move :

δ

0

1

q0

{q2,q3}

{ }

q1

{q2,q3}

{ }

q2

q3

q1

q3

q3

q1

 


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