1

0

1

0

1 1

0

q0 , q1 , q2 , q3 , q4, q5

0,1

q0

q3 , q4

Nama : Dhita Pratiwi

Nim : 131421030

Kelas : Kom A Ekst Ilmu komputer USU

Hari / Tanggal : Rabu, 23 Oktober 2013

Mata Kuliah : Teori Bahasa dan Otomata (TBO)

Dosen : Drs. Agus Salim Harahap, M.Sc

Tugas

1. Lakukan Reduksi jumlah state pada DFA berikut :

Jawab :

Dik : Q =

=

S =

F =

Reduksi adalah Mengurangi jumlah state dengan tidak mengurangi

kemampuannya semula untuk menerima suatu bahasa.

0,1

q0

q1

q2q5

q3

q4 0,1

0

0,1

0,1 1

Penyelesaian:Tahap – tahap yang dilakukan untuk reduksi jumlah state adalah sebagai berikut :

1. State yang tidak tercapai dari state awal yaitu q5. Maka q5 dihapus.

2. q0, q1, q2, € F

q3, q4 € F

3. Distinguishable : ( q0, q1 ), ( q0, q4 ), ( q1, q3 )

( q1, q4 ), ( q2, q3 ), ( q2, q4 )

4. State – state distinguishable yang lain :

( q0, q1 ) → µ ( q0, 1 ) = q2

µ ( q1, 1 ) = q3

karena (q2, q3) distinguishable, maka (q0, q1) distinguishable

( q0, q2 ) → µ ( q0, 1 ) = q2

µ ( q2, 1 ) = q4

karena (q2, q4) distinguishable, maka (q0, q2) distinguishable

5. Distinguishable : (q0, q1), (q0, q2), (q0, q3), (q0, q4)

(q1, q3), (q1, q4), (q2, q3), (q2, q4)

Indistinguishable : (q1, q2), (q3, q4)

6. q1 dan q2 saling indistinguishable

q3 dan q4 saling indistinguishable

Jadi, gambar Mesin DFA setelah di Resuksi adalah :

q0

q1,

2

q3

,4

0