Quiz TBO Kelompok 11

Apa perbedaan utama antara Deterministic Finite State Automata (DFA) dan Non Deterministik Finite State Automata (NFA)?

• DFA memiliki satu keadaan awal, sedangkan NFA dapat memiliki beberapa keadaan awal.

• DFA hanya dapat membaca satu simbol input pada suatu waktu, sedangkan NFA dapat membaca beberapa simbol input secara bersamaan.

• DFA memiliki fungsi transisi yang unik untuk setiap pasangan keadaan dan simbol input, sedangkan NFA dapat memiliki lebih dari satu pilihan transisi untuk pasangan tersebut.

• DFA selalu menerima atau menolak input, sedangkan NFA hanya dapat menerima input.

Diberikan NFA dengan keadaan awal q0 dan keadaan akhir qf. Apa yang dapat dikatakan tentang string yang diterima oleh NFA?

• String diterima jika dan hanya jika string tersebut melewati keadaan q0.

• String diterima jika dan hanya jika ada jalur yang menghubungkan q0 dan qf yang sesuai dengan string tersebut.

• String diterima jika dan hanya jika string tersebut mengandung simbol yang diakui oleh NFA.

• String diterima jika dan hanya jika panjangnya sesuai dengan jumlah keadaan dalam NFA.

Manakah pernyataan berikut yang benar tentang kekuatan ekspresif NFA dibandingkan dengan DFA?

• NFA lebih lemah daripada DFA dalam hal kekuatan ekspresif.

• NFA dan DFA memiliki kekuatan ekspresif yang setara.

• NFA lebih kuat dalam hal kekuatan ekspresif karena dapat mengenali bahasa yang tidak dapat dikenali oleh DFA.

• DFA lebih kuat karena dapat mengenali bahasa konteks-bebas, sedangkan NFA tidak dapat.

Sebuah NFA memiliki dua keadaan awal (start states) dan satu keadaan akhir (final state). Bagaimana pengaruh keberadaan keadaan awal ganda terhadap kemampuan NFA dalam mengenali string?Tidak ada pengaruh, karena keadaan awal dapat diabaikan.

• Tidak ada pengaruh, karena keadaan awal dapat diabaikan.

• Menambah kompleksitas, tetapi tidak memengaruhi kemampuan.

• Meningkatkan kemampuan NFA untuk mengenali string yang lebih kompleks.

• Mengurangi kemampuan NFA untuk mengenali string yang benar.

Berapakah jumlah state maksimum yang dapat dimiliki NFA dalam sebuah finite language?

• 10

• 7

• 15

• Tidak Terbatas

Perhatikan gambar berikut!
Tentukan inputan manakah yang diterima

• aabb

• abab

• abba

• semua benar

Dari gambar tersebut, terdapat berapa transisi yang menginputkan nilai yang berbeda untuk setiap state yang sama?

• 2 untuk setiap state

• 4 terhadap state yang menerima

• 2 tanpa deklarasi state

• semua benar