Quiz Teori Bahasa dan Otomata

Apa yang dimaksud dengan ekuivalensi dalam konteks NFA dan DFA?

• Keadaan di mana dua mesin menerima bahasa yang berbeda

• Keadaan di mana dua mesin memiliki jumlah state yang sama

• Keadaan di mana dua mesin dapat menerima bahasa yang sama

• Keadaan di mana dua mesin memiliki tabel transisi yang identik

Apa kepanjangan dari DFA dalam teori bahasa dan otomata?

• Deterministic Final Automaton

• Deterministic Finite Automaton

• Dynamic Finite Automaton

• Dual Finite Automaton

Apa perbedaan utama antara DFA dan NFA?

• NFA tidak memiliki state awal, sedangkan DFA memiliki

• DFA hanya memiliki satu kemungkinan transisi untuk setiap input di setiap state, sedangkan NFA bisa memiliki lebih dari satu

• NFA hanya menerima string kosong, sedangkan DFA tidak

• DFA lebih kompleks daripada NFA dalam hal jumlah state

Dalam proses konversi dari NFA ke DFA, apa yang harus dilakukan terhadap state yang tidak memiliki transisi lebih lanjut?

• Menghapus state tersebut dari DFA

• Menjadikan state tersebut sebagai final state

• Menambahkan state ∅ (kosong) sebagai transisi akhir

• Mengubah semua transisi menjadi mengarah ke state awal

Jika sebuah state {q0, q1} dalam DFA menerima input ‘1’, dan hasilnya d(q0,1) = {q1} serta d(q1,1) = {q0, q1}, maka hasilnya adalah?

• {q1}

• {q0}

• {q0, q1}

• ∅