Teori Bahasa Otomata (TBO) – Ekuivalensi NFA – DFA


EKUIVALENSI NFA-DFA
Ada apa dengan NFA ? konsep yang sulit diimplemen-tasikan. Komputer sepenuhnya deterministic.
Kenapa dipelajari ? Lebih dekat ke sistem nyata
Contoh : permainan catur, banyak alternatif pada suatu posisi tertentu -> nondeterministic

Algoritma :

  1. Buat semua state yang merupakan subset dari state semula. jumlah state menjadi 2Q
  2. Telusuri transisi state–state yang baru terbentuk, dari diagram transisi.
  3. Tentukan state awal : {q0}
  4. Tentukan state akhir adalah state yang elemennya mengandung state akhir.
  5. Reduksi state yang tak tercapai oleh state awal.
  6. Rename nama-nama state yang tersisa.

Download Materi Selengkapnya: Disini

Iklan

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s