Maaf, Anda mengaktifkan Adblock pada browser anda!
Atau anda tidak mengaktifkan Javascript![ Disable Your AdBlock Please ]
Home > Teori Bahasa dan Automata > Equivalensi NonDeterministic Finite Automata (NFA) dengan ε-move ke NonDeterministic Finite Automata (NFA) tanpa ε-move

Equivalensi NonDeterministic Finite Automata (NFA) dengan ε-move ke NonDeterministic Finite Automata (NFA) tanpa ε-move

Contoh soal :

Jika disajikan dalam tabel transisi :
d
a
b
q0
{q0}
Ø
q1
Ø
{q2}
Q2
Ø
{q2}

Kemudian kita entukan ε-cl untuk setiap statenya :

ε-cl (q0) = {q0,q1}
ε-cl (q1) = {q1}
ε-cl (q2) = {q0,q1,q2}
Selanjutnya kita tentukan d sebagai berikut :
d (q0,a)   = ε-cl (  d ( ε-cl (q0), a) )
                 = ε-cl (  d ( {q0,q1}, a) )
                 = ε-cl ( q0 )
                 = {q0,q1}
d (q0,a)   = ε-cl (  d ( ε-cl (q0), b) )
                 = ε-cl (  d ( {q0,q1}, b) )
                 = ε-cl ( q2 )
                 = {q0,q1,q2}
d (q1,a)   = ε-cl (  d ( ε-cl (q1), a) )
                 = ε-cl (  d ( {q1}, a) )
                 = ε-cl ( Ø )
                 = Ø
d (q1,b)   = ε-cl (  d ( ε-cl (q1), b) )
                 = ε-cl (  d ( {q1}, b) )
                 = ε-cl ( q2 )
                 = {q0,q1,q2}
d (q2,a)   = ε-cl (  d ( ε-cl (q2), a) )
                 = ε-cl (  d ( {q0,q1,q2}, a) )
                 = ε-cl ( q0 )
                 = {q0,q1}
d (q2,b)   = ε-cl (  d ( ε-cl (q2), b) )
                 = ε-cl (  d ( {q0,q1,q2}, b) )
                 = ε-cl ( q2 )
                 = {q0,q1,q2}
Berdasarkan hasil diatas dapat kita buat tabel transisi untuk NFA tanpa ε-move sebagai berikut.
d
a
b
q0
{q0,q1}
{q0,q1,q2}
q1
Ø
{q0,q1,q2}
q2
{q0,q1}
{q0,q1,q2}

Kemudian kita tentukan himpunan stateakhir untuk Non,determinitic Finite Automata tanpa ε-move ini.
Himpunan state akhir semula adalah {q0}. Kita lihat ε-cl(q2) = {q0,q1,q2} sehingga himpunan state akhir sekarang {q0,q2}.

Leave a Reply

Your email address will not be published. Required fields are marked *

*