49 Soal Teori Otomata Beserta Jawaban
Kumpulan Soal Pilihan Ganda Materi Teori Otomata
1. Dalam teori otomata, otomata digunakan untuk menggambarkan:
A. Proses algoritma
B. Struktur data
C. Program komputer
D. Sistem formal
Jawaban:
D. Sistem formal
2. Yang bukan merupakan jenis otomata adalah:
A. Otomata deterministik terbatas
B. Otomata tak deterministik terbatas
C. Mesin Turing
D. Mesin von Neumann
Jawaban:
D. Mesin von Neumann
3. Apakah otomata yang mampu menerima bahasa dengan pola "abba"?
A. Otomata DFA
B. Otomata NFA
C. Otomata PDA
D. Otomata Turing
Jawaban:
A. Otomata DFA
4. Yang termasuk komponen utama dalam otomata adalah:
A. Stack
B. Registers
C. Input/output
D. States
Jawaban:
D. States
5. Apa kepanjangan dari DFA dalam teori otomata?
A. Deterministic Finite Automaton
B. Deterministic Formal Automaton
C. Deterministic Finite Algorithm
D. Deterministic Formal Algorithm
Jawaban:
A. Deterministic Finite Automaton
6. Otomata tak deterministik memiliki jumlah yang lebih besar dibandingkan otomata deterministik dalam hal apa?
A. Jumlah keadaan
B. Jumlah alfabet
C. Jumlah fungsi transisi
D. Jumlah input
Jawaban:
C. Jumlah fungsi transisi
7. Apakah jenis otomata yang cocok digunakan untuk mengenali bahasa yang dihasilkan oleh tata bahasa alami?
A. Otomata DFA
B. Otomata NFA
C. Otomata PDA
D. Otomata Turing
Jawaban:
D. Otomata Turing
8. Apakah istilah yang digunakan untuk menggambarkan bahasa yang dapat diterima oleh otomata tertentu?
A. Bahasa kritis
B. Bahasa tertutup
C. Bahasa otomata
D. Bahasa bebas konteks
Jawaban:
C. Bahasa otomata
9. Berapa banyak keadaan maksimum yang dapat dimiliki oleh otomata DFA dengan alfabet berukuran n?
A. n
B. n+1
C. 2n
D. 2^n
Jawaban:
D. 2^n
10. Apakah otomata yang mampu menerima bahasa dengan pola "a^n b^n"?
A. Otomata DFA
B. Otomata NFA
C. Otomata PDA
D. Otomata Turing
Jawaban:
C. Otomata PDA
11. Pernyataan yang benar tentang otomata NFA adalah:
A. Setiap simbol input memiliki tepat satu fungsi transisi yang terdefinisi.
B. Otomata NFA tidak memiliki fungsi transisi epsilon.
C. Otomata NFA dapat berada dalam beberapa keadaan secara bersamaan.
D. Otomata NFA hanya dapat mengenali bahasa reguler.
Jawaban:
C. Otomata NFA dapat berada dalam beberapa keadaan secara bersamaan.
12. Manakah yang termasuk bahasa tidak berhingga?
A. Bahasa kosong
B. Bahasa berhingga
C. Bahasa terhitung
D. Bahasa tak terhitung
Jawaban:
D. Bahasa tak terhitung
13. Otomata yang memiliki kemampuan untuk membaca dan menulis pada sel-selnya adalah:
A. Otomata non-deterministik
B. Mesin Turing
C. Mesin von Neumann
D. Otomata dengan pita tak terbatas
Jawaban:
B. Mesin Turing
14. Yang bukan merupakan bagian dari otomata pushdown adalah:
A. Stack
B. Alfabet input
C. States
D. Fungsi transisi
Jawaban:
B. Alfabet input
15. Apakah yang dimaksud dengan otomata non-deterministik?
A. Otomata yang hanya memiliki satu kemungkinan jalur eksekusi.
B. Otomata yang dapat memilih jalur eksekusi dari beberapa opsi yang ada.
C. Otomata yang hanya memiliki satu keadaan awal.
D. Otomata yang tidak memiliki keadaan final.
Jawaban:
B. Otomata yang dapat memilih jalur eksekusi dari beberapa opsi yang ada.
16. Dalam teori otomata, ekspresi yang menggambarkan langkah-langkah perhitungan pada otomata disebut:
A. Algoritma
B. Fungsi transisi
C. Ekspresi reguler
D. Fungsi rekursif
Jawaban:
B. Fungsi transisi
17. Otomata yang mampu mengenali bahasa konteks bebas adalah:
A. Otomata DFA
B. Otomata NFA
C. Otomata PDA
D. Otomata Turing
Jawaban:
C. Otomata PDA