PERTEMUAN IX TEORI BAHASA DAN AUTOMATA
ubahlah Ekuivalensi Non –
Deterministic Finite Automata dengan Є – Move pada gambar diatas kedalam Non
Deterministic Finite Automata tanpa Є-Move!
JAWAB
1. Buatlah tabel transisi dari NFA є – move di atas.
2. Tentukan є-closure untuk setiap state Є – Closure
( q0 ) = { q0, q1 }
Є – Closure (q1 ) =
{ q1 }
Є – Closure (q2 ) =
{ q0, q1, q2 }
3. Carilah setiap fungsi transisi
hasil dari pengubahan NFA є – move ke NFA tanpa є –move. Fungsi transisi itu
ditandai dengan simbol δ’
δ
(q0 , a ) = є_cl (δ (є_cl(q0),a))
= є_cl (q0)δ’ (q0 , b ) = є_cl
(δ (є_cl(q0),b))= є_cl (q2)= { q0, q1 , q2}
δ’ (q1 , a ) =
є_cl (δ (є_cl(q1),a))
= є_cl (Ø )
= Ø
δ’ (q1 , b ) = є_cl (δ (є_cl(q1),b))
= є_cl (q2)
= { q0, q1 ,
q2}
δ’ (q2 , a ) = є_cl (δ (є_cl(q2),a))
= є_cl (q0)
= { q0, q1 }
δ’ (q2 , b ) = є_cl (δ (є_cl(q2),b))
= є_cl (q2)
= { q0, q1 ,
q2}
4. Buatlah
tabel transisi dari fungsi transisi yang telah dibuat pada langkah sebelumnya.
5. Kemudian,
tentukanlah himpunan state akhir untuk
NFA tanpa є – move ini. Himpunan state akhir
semula adalah {q0}. Kita lihat є_cl (q2) = { q0, q1 , q2} , maka
himpunan state akhir sekarang adalah {q0, q2 }. Sehingga diperoleh diagram
transisi sebagai berikut:
