Quiz 5 Teori Bahasa dan Otomata 2021-1

Pada mesin NFA semula, himpunan state akhir adalah {q1}

Maka pada DFA hasil perubahan state-state akhir adalah

• semua state yang mengandung {q1}.

• semua state di luar mengandung {q1}.

• semua state beririsan dengan {q1}.

• semua state yang mengandung {p1}.

• semua jawaban di atas salah

Dari sebuah mesin Non-deterministic Finite Automata (NFA) dapat dibuat mesin Deterministic Finite Automata (DFA)-nya yang

• ekuivalen (bersesuaian).

• berlawanan arah

• berjejer searah

• memunculkan arah baru

• arahnya tidak jelas

Ekuivalen disini artinya

• mampu menerima bahasa yang sama.

• sama persis

• sama mirip

• berbeda-beda

• sama rahnya

Selanjutnya kita telusuri state berikutnya yang diperoleh dengan memanfaatkan tabel transisinya:

- state {q0} bila memperoleh input 0 menjadi state {q0,q1}.

- state {q0} bila memperoleh input 1 menjadi state {q1}.

Hasilnya seperti gambar di atas: Selanjutnya, kita telusuri state-state baru yg terbentuk kecuali:

• :State {q1} bila memperoleh input O menjadi state Ø; •

• State {q} bila memperoleh input i menjadi state {90,91};

• State {qo,,} bila memperoleh input O menjadi state {qo,,}, ini diperoleh dari 8 (90,0)={qo,,} digabung dengan (91,0)=0, maka hasilnya d ({90,9,},0)={90,9;};

• State {qo,,} bila memperoleh input i menjadi state {qo,9,}, ini diperoleh dari 8(90,1)= digabung dengan 8(91,1)={90,9,}, maka hasilnya 8({90,9,3,1)={90,92}.

• State - statenya tidak dapat diidentifikasi

Perhatikan gambar di atas:

bahwa state {q1}, menerima input 0 menjadi state Ø, disini Ø kita gambarkan juga sebagai .....................

• sebuah state.

• tujuan state

• hasil state

• puncak state

• akhir state