0

Ekivalensi Non Deterministic Finite Automata dengan Deterministic Finite Automata

Posted by Jujur Sitanggang on 5:57 AM

     Dari sebuah NFA dapat dibuat bentuk DFA nya yang ekivalen (bersesuaian). Ekivalen disini artinya mampu memproduksi atau menerima bahasa yang sama. Adapun tahap pembuatan DFA yang ekivalen dari suatu NFA adalah sebagai berikut:
Contoh 4  Diketahui NFA sebagai berikut





Konfigurasi NFA contoh 4 secara formal adalah sebagai berikut :
Q = {q0, q1 }
S = {0, 1}
S = q0
F = {q1}
Tabel transisinya :
d
0
1
q0
{q0, q1}
{q1}
q1
Ø
{q0, q1}


Telusuri state berikutnya :  (d = teta)
·               d (q0, 0) = {q0, q1 }
·               d (q0, 1) = {q1}
Hasilnya : 









-                Selanjutnya telusuri untuk setiap state baru yang terbentuk :
·               d (q1, 0) = Ø
·               d (q1, 1) = {q0, q1}
·               d ({q0,q1}, 0) = {q0, q1} adalah hasil gabungan dari
d (q0, 0) = {q0, q1}dengan d (q1, 0) = Ø
·               d ({q0,q1}, 1) = {q0, q1} adalah hasil gabungan dari
d (q0, 1) = {q1}dengan d (q1, 0) = {q0, q1}


Hasilnya  :


-                Selanjutnya telusuri state baru yang terbentuk :
·               d (Ø, 0) = Ø
·               d (Ø, 0) = Ø
Hasilnya :


-                Selanjutnya kita ingat bahwa F = {q1} maka himpunan state akhir (F) sekarang adalah semua yang mengandung state q1. 
F = {{q1}, {q0, q1}}
Hasilnya :








0 Comments

Copyright Jujur Soaloon Sitangang Lipan All rights reserved. Theme by Sitanggang. | Bloggerized by Soalparna.