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 state
akhir 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}.
0 Comments