Ekuivalensi NFA (Nondeterministic Finite Automata) Ke DFA (Deterministic Finite Automata)

-

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


        Dari sebuah mesin Non-deterministic Finite Automata dapat dibuat mesin DFA yang ekivalen. Ekivalen artinya mampu menerima bahasa yang sama.

Simulasi NFA ke DFA

  • Cara simulasi NFA ke DFA adalah dengan menbuat state DFA berkorespondensi dengan set state di NFA.
  • DFA yang dibentuk mencatat semua state yang mungkin pada NFA setelah membaca input tertentu.

FSA (Finite State Automata) 

FSA terdiri dari :
1. DFA (Deterministic Finite Automata)
2. NFA (Non-deterministic Finite Automata)

Ciri DFA dan NFA

1. Ciri DFA (Deterministic Finite Automata)




2. Ciri NFA (Non-deterministic Finite Automata)



Proses Ekuivalensi NFA Ke DFA

  • Buat tabel transisi diagram tersebut
  • Buat diagram transisi untuk FSA diatas

Setiap State dituliskan sebagai humpunan state {}
  • Buat tabel transisi baru
  • Buat diagram transisi ekuivalensi NFA ke DFA

Contoh Lainnya :






Komentar

Posting Komentar

Postingan populer dari blog ini

NFA (Nondeterministic Finite Automata) Dengan E-Move

-
Gambar
 NFA (Nondeterministic Finite Automata) Dengan E-Move Proses Perpindahan State Tanpa Membawa Nilai Input Apapun (empty). NFA Dengan E-Move              NFA dengan E-Move (transisi E-Move), diperbolehkan merubah state tanpa membaca input. Disebut dengan E-Move karena tidak bergantung pada 1 input saat melakukan transisi (perpindahan). E-Move Berada Pada Transisi State         Sebuah transisi mempunyai nilai/output/E-Move. Suatu E-Move untuk state q1 ke q2 yang terhubung dapat berpindah tanpa menghasilkan inputan apapun pada transisinya. Contoh : Tanpa membaca inputan : q0 dapat berpindah ke q1 q1 dapat berpindah ke q2 q4 dapat berpindah ke q1 E-Clouser  E-Closure adalah himpunan state yang dapat di capai dari suatu state tanpa membaca input. E-Closure (q0) = himpunan state yang dapat dicapai dari state q0 tanpa membaca input. Pada suatu state yang tidakk memiliki E-Move maka E-Closure nya adalah state itu sendiri....
Baca selengkapnya

FSA (Finite State Automata) & DFA (Deterministic Finite Automata)

-
Gambar
 FSA (Finite State Automata) &  DFA (Deterministic Finite Automata) Definisi Formal FSA  M = (Q, Σ, 8, S, F)  dimana :  Q = himpunan state Σ = abjad, himpunan simbol input/masukan 8 = fungsi transisi, 8 = Q * Σ -> Q S = state awal / initial state F = himpunan state akhir / final state Jenis DFA Deterministik (DFSA/DFA) Pada setiap input, hanya ada satu keadaan (state) tujuan dari keadaan saat ini. Non - Deterministik (NFSA/NFA) Pada setiap input terdapat lebih dari satu keadaan tujuan dari keadaan saat ini. Contoh DFA  Contoh DFA yang dapat menerima string berakhiran 01  A = ({q0, q1, q2}, {0, 1}, 8, q0, {q2}) dengan fungsi transisi 8 diberikan dalam bentuk table : Contoh Lainnya :
Baca selengkapnya