16 Soal Tentang Teori Otomata + Kunci Jawaban
Latihan Soal PG Bab Teori Otomata
1. Dalam teori otomata, istilah yang digunakan untuk menggambarkan bahasa yang tidak dapat dikenali oleh otomata adalah:
A. Bahasa non-konteks bebas
B. Bahasa tak terhingga
C. Bahasa tak berhingga
D. Bahasa tidak dapat diterima
Jawaban:
A. Bahasa non-konteks bebas
2. Otomata yang mampu menerima bahasa dengan pola "0^n 1^n" adalah:
A. Otomata DFA
B. Otomata NFA
C. Otomata PDA
D. Otomata Turing
Jawaban:
B. Otomata NFA
3. Yang bukan merupakan jenis otomata berdasarkan kekuatan komputasi adalah:
A. Otomata deterministik terbatas
B. Otomata tak deterministik terbatas
C. Mesin Turing
D. Mesin von Neumann
Jawaban:
D. Mesin von Neumann
4. Pernyataan yang benar tentang otomata deterministic finite automaton (DFA) adalah:
A. DFA dapat memiliki beberapa keadaan awal.
B. DFA dapat memiliki fungsi transisi epsilon.
C. DFA hanya dapat berada dalam satu keadaan pada suatu waktu.
D. DFA selalu dapat mengenali bahasa konteks bebas.
Jawaban:
C. DFA hanya dapat berada dalam satu keadaan pada suatu waktu.
5. Otomata yang dapat mengenali bahasa dengan pola "ab*" adalah:
A. Otomata DFA
B. Otomata NFA
C. Otomata PDA
D. Otomata Turing
Jawaban:
B. Otomata NFA
6. Dalam teori otomata, istilah yang digunakan untuk menggambarkan jalur eksekusi yang menghasilkan output pada otomata adalah:
A. Transisi
B. Konfigurasi
C. Iterasi
D. Rekursi
Jawaban:
B. Konfigurasi
7. Apakah yang dimaksud dengan otomata dengan pita tak terbatas?
A. Otomata yang memiliki pita input dengan panjang yang tidak terbatas.
B. Otomata yang memiliki jumlah keadaan tak terbatas.
C. Otomata yang memiliki alfabet input tak terbatas.
D. Otomata yang dapat membaca dan menulis pada sel-selnya tanpa batasan.
Jawaban:
D. Otomata yang dapat membaca dan menulis pada sel-selnya tanpa batasan.
8. Pernyataan yang benar tentang hubungan antara bahasa reguler dan bahasa konteks bebas adalah:
A. Setiap bahasa reguler juga merupakan bahasa konteks bebas.
B. Setiap bahasa konteks bebas juga merupakan bahasa reguler.
C. Bahasa reguler dan bahasa konteks bebas tidak dapat saling dikonversi.
D. Bahasa reguler selalu lebih kuat daripada bahasa konteks bebas.
Jawaban:
A. Setiap bahasa reguler juga merupakan bahasa konteks bebas.
9. Dalam teori otomata, istilah yang digunakan untuk menggambarkan proses mengubah satu keadaan otomata ke keadaan berikutnya berdasarkan input adalah:
A. Transisi
B. Konfigurasi
C. Iterasi
D. Rekursi
Jawaban:
A. Transisi
10. Otomata yang mampu mengenali bahasa dengan pola "a^nb^m" adalah:
A. Otomata DFA
B. Otomata NFA
C. Otomata PDA
D. Otomata Turing
Jawaban:
C. Otomata PDA
11. Pernyataan yang benar tentang otomata non-deterministik adalah:
A. Setiap otomata non-deterministik dapat diubah menjadi otomata deterministik yang setara.
B. Setiap otomata deterministik dapat diubah menjadi otomata non-deterministik yang setara.
C. Otomata non-deterministik dan otomata deterministik tidak dapat saling dikonversi.
D. Otomata non-deterministik selalu lebih kuat daripada otomata deterministik.
Jawaban:
A. Setiap otomata non-deterministik dapat diubah menjadi otomata deterministik yang setara.
12. Apakah yang dimaksud dengan bahasa konteks bebas dalam teori otomata?
A. Bahasa yang dapat dihasilkan oleh otomata Turing.
B. Bahasa yang dapat dikenali oleh otomata Turing.
C. Bahasa yang tidak dapat dikenali oleh otomata Turing.
D. Bahasa yang tidak dapat dihasilkan oleh otomata Turing.
Jawaban:
A. Bahasa yang dapat dihasilkan oleh otomata Turing.
13. Pernyataan yang benar tentang hubungan antara otomata dengan pita tak terbatas dan mesin Turing adalah:
A. Setiap otomata dengan pita tak terbatas dapat diubah menjadi mesin Turing yang setara.
B. Setiap mesin Turing dapat diubah menjadi otomata dengan pita tak terbatas yang setara.
C. Otomata dengan pita tak terbatas dan mesin Turing memiliki kemampuan yang setara dalam hal pengenalan bahasa.
D. Otomata dengan pita tak terbatas selalu lebih kuat daripada mesin Turing dalam hal kemampuan komputasi.
Jawaban:
C. Otomata dengan pita tak terbatas dan mesin Turing memiliki kemampuan yang setara dalam hal pengenalan bahasa.
14. Otomata yang mampu menerima bahasa dengan pola "a^n" atau "b^n" adalah:
A. Otomata DFA
B. Otomata NFA
C. Otomata PDA
D. Otomata Turing
Jawaban:
B. Otomata NFA
15. Pernyataan yang benar tentang otomata dengan pita tak terbatas adalah:
A. Otomata dengan pita tak terbatas dapat mengenali semua bahasa reguler.
B. Otomata dengan pita tak terbatas hanya dapat membaca input dari kiri ke kanan.
C. Otomata dengan pita tak terbatas tidak memerlukan fungsi transisi.
D. Otomata dengan pita tak terbatas selalu memiliki jumlah keadaan yang terbatas.
Jawaban:
A. Otomata dengan pita tak terbatas dapat mengenali semua bahasa reguler.
16. Apakah yang dimaksud dengan operasi potongan dalam teori otomata?
A. Menggabungkan dua otomata menjadi satu otomata baru.
B. Menggabungkan alfabet input otomata menjadi satu simbol.
C. Menggabungkan beberapa fungsi transisi menjadi satu fungsi transisi yang kompleks.
D. Menyusun fungsi transisi otomata dalam urutan tertentu.
Jawaban:
A. Menggabungkan dua otomata menjadi satu otomata baru.