Merubah NFA Dengan E - Move Ke NFA Tanpa E - Move

Dari  sebuah Non-deterministic  Finite  Automata  dengan E -move  dapat  kita peroleh Non-  deterministic  Finite  Automata  tanpa E -move  yang  ekivalen. Berikut ini diberikan beberapa contoh NFA dengan E - Move dan tanpa E - Move.


Gambar 1. NFA dengan E - Move

Pada gambar diatas terlihat bahwa q0 membawa sebuah input empty ke q1. Sedangkan berikut dibawah ini gambar NFA tanpa E - Move


Gambar 2. NFA tanpa E - Move


Berikut tahapan  untuk  mendapatkan perubahan dari Non-deterministic Finite Automata E - move  ke Non - deterministic Finite Automata tanpa E -move. Caranya  secara  umum adalah sebagai berikut:

  1. Buat table transisi Non-deterministic Finite Automata dengan E - move semula
  2. Tentukan E - closure untuk setiap state
  3. Carilah   setiap   fungsi   transisi   hasil   perubahan   dari   Non-deterministic Finite Automata E - move  ke Non-deterministic Finite Automata  tanpa E - move (kita sebut saja sebagai ε’) dimana ε’ didapatkan dengan rumus:ε’(state, input) = ε_closure (δ(ε_closure(state, input)).
  4. Berdasarkan hasil no (3), kita bisa membuat table transisi dan diagram transisi dari Non-deterministic Finite  Automata  tanpa ε-move yang  ekivalen  dengan Non-deterministic Finite Automata ε-move tersebut.
  5. Jangan lupa menentukan state-state akhir untuk Non-deterministic Finite Automatatanpa ε-move tersebut, yaitu state-state akhir semula ditambah dengan state-state yang ε_closure –nya menuju ke salah satu dari state akhir semula. Dalam bahasa formalnya:
       F' = F ∪ {q | (ε-closure(q) ∩ F) ≠ ∅}


Contoh Soal:













Comments

Post a Comment

Popular posts from this blog

Ekuivalensi Antar Deterministic Finite Automata (DFA)

Image
Ekuivalensi Antar Deterministic Finite Automata (DFA)  Tujuan: Mengurangi jumlah state dari suatu Finite State Automata,dengan tidak mengurangi kemampuannya semula untuk menerima suatu bahasa. Pasangan state dapat dikelompokkan berdasarkan: 1. Distinguishable State (Dapat Dibedakan) 2. Ind istinguishable State (Tidak Dapat Dibedakan) 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. Biasanya DFA diwakili oleh 5-tuple (Q, ∑, δ,Q0, F) dimana: Q adalah himpunan terbatas state. ∑ adalah himpunan terbatas simbol yang disebut alfabet. δ adalah fungsi transisi di mana δ: Q × ∑ → Q q0 adalah keadaan awal dari mana input diproses (Q0∈ Q). F adalah himpunan keadaan akhir/keadaan akhir dari Q (F ⊆ Q). Contoh Sebuah Mesin DFA Lakukan reduksi pada ...
Read more

Hierarki Chomsky

Image
Apa Itu Teori Bahasa & Otomata Teori bahasa dan automata adalah bagian dari teori komputasi ilmu komputer. Bagian dari teori komputer berasal dari bahasa dan desain sistem, terutama yang berbasis matematika. Dalam hal ini, fokusnya adalah pada pemecahan masalah. Dengan menggunakan contoh-contoh yang menggambarkan masalah, latar belakang konsep dan hubungannya dengan definisi dan teorema yang ada dapat diidentifikasi.  Teori bahasa dan automata diterapkan pada beberapa model digital, misalnya  tentang pengembangan bahasa pemrograman dan kompiler. Meskipun tujuannya adalah untuk belajar teori  Bahasa dan robot itu sendiri, yaitu. menambahkan dasar-dasar teori bahasa formal dan model mesin matematika yang menjelaskan cara kerja komputer. Biasanya kita hanya mengenal bahasa seperti bahasa Inggris atau bahasa Indonesia.  Bahasa adalah sekumpulan string abjad, sedangkan  String itu sendiri adalah kata (kombinasi huruf) dalam bahasa, contoh rantai  "Wayan Chan...
Read more