NEW
Font size
WorksheetsKelompok 4 - Teori Bahasa dan Otomata (NFA)
Total questions: 10
Worksheet time: 4mins
Perbedaan utama antara Deterministic Finite Automata (DFA) dan Nondeterministic Finite Automata (NFA) yaitu?
DFA dapat memiliki lebih banyak keadaan daripada NFA
DFA hanya dapat melakukan transisi satu keadaan untuk satu simbol masukan, sedangkan NFA dapat memiliki lebih dari satu transisi untuk satu simbol masukan dari satu keadaan
NFA selalu lebih efisien dalam pengenalan bahasa daripada DFA
DFA dan NFA memiliki kekuatan pengenalan bahasa yang setara
Pada gambar berikut, bila state q0 mendapat input 'a' maka bisa berpindah ke state q0 atau q1. Maka secara formal dinyatakan?
δ (q0, a) = {q0, q1}
δ (q1, a) = {q0, q1}
δ (q0, b) = {q0, q1}
δ (q1, b) = {q0, q1}
Simbol "ε (epsilon)” dalam konteks NFA memiliki arti sebagai?
Transisi yang hanya terjadi jika tidak ada simbol masukan
Tanpa masukan atau transisi kosong
Transisi yang hanya terjadi pada keadaan akhir
Transisi yang mengarah ke keadaan awal
Manakah pernyataan berikut yang benar mengenai NFA?
NFA hanya memiliki satu keadaan akhir
NFA tidak dapat menerima string kosong (ε).
Semua NFA dapat dikonversi ke DFA (Deterministic Finite Automata)
NFA selalu memiliki lebih banyak keadaan dibandingkan DFA yang menerima bahasa yang sama
Secara formal FSA dinyatakan oleh 5 tupel, dimana
M = {Q, Σ, δ, q0, F}
Manakah arti simbol berikut yang salah?
Q = Himpunan state
Σ = Himpunan simbol input
δ = Himpunan state akhir
q0 = State awal q0, dimana q0 ε Q
Bagaimana NFA menentukan apakah sebuah string masukan diterima atau ditolak?
Mengevaluasi semua kemungkinan transisi dan mengamati apakah salah satu jalur mencapai final state
Menghitung jumlah transisi yang dilakukan
Menghitung probabilitas keadaan akhir yang dicapai
Mengabaikan transisi-transisi yang tidak valid
Berapa jumlah keadaan akhir (final state) yang dapat dimiliki oleh NFA?
Tidak bisa memiliki keadaan awal
Hanya satu
Lebih dari satu
Terbatas oleh jumlah keadaan
Perhatikan pada gambar berikut, apa yang terjadi jika NFA berada di keadaan q1 dan menerima simbol masukan “b”?
NFA akan mengalami keadaan tidak valid
NFA akan melakukan transisi ke q0
NFA akan melakukan transisi ke q1 dan q0 secara bersamaan
NFA akan tetap berada di keadaan q1
Manakah dari pernyataan berikut yang benar tentang NFA?
I. State akhir pada NFA menunjukkan bahwa input diterima
II. NFA dapat diubah menjadi DFA tanpa kehilangan keekspresifan bahasa
III. NFA dapat memiliki transisi ke lebih dari satu state untuk simbol input yang sama
I dan II
II dan III
I dan III
Semua pernyataan benar
Apa yang dimaksud dengan transisi yang tidak pasti pada NFA?
Transisi yang dilakukan dengan peluang tertentu
Transisi yang hanya terjadi pada keadaan awal
Transisi yang dapat dilakukan tanpa mengetahui input selanjutnya
Transisi yang harus dilakukan untuk mengakhiri input
