16 Soal (Pilihan Ganda) Teori Otomata dan Jawaban
Contoh Soal Pilgan Tentang Teori Otomata
1. Pernyataan yang benar tentang bahasa yang diterima oleh otomata Turing adalah:
A. Bahasa yang dapat diterima oleh otomata Turing merupakan subset dari bahasa yang dapat diterima oleh otomata DFA.
B. Bahasa yang dapat diterima oleh otomata Turing merupakan superset dari bahasa yang dapat diterima oleh otomata NFA.
C. Bahasa yang dapat diterima oleh otomata Turing tidak termasuk bahasa konteks bebas.
D. Bahasa yang dapat diterima oleh otomata Turing termasuk dalam kelas bahasa rekursif secara keseluruhan.
Jawaban:
D. Bahasa yang dapat diterima oleh otomata Turing termasuk dalam kelas bahasa rekursif secara keseluruhan.
2. Pernyataan yang benar tentang hubungan antara otomata tak deterministik dan otomata deterministik adalah:
A. Setiap otomata tak deterministik dapat dikonversi menjadi otomata deterministik yang setara.
B. Setiap otomata deterministik dapat dikonversi menjadi otomata tak deterministik yang setara.
C. Otomata tak deterministik dan otomata deterministik tidak dapat saling dikonversi.
D. Otomata tak deterministik selalu lebih kuat daripada otomata deterministik.
Jawaban:
A. Setiap otomata tak deterministik dapat dikonversi menjadi otomata deterministik yang setara.
3. Dalam teori otomata, konsep yang menggambarkan kemampuan otomata untuk mengingat informasi sebelumnya adalah:
A. Memori
B. Stack
C. Registers
D. Input/output
Jawaban:
A. Memori
4. Apa yang dimaksud dengan bahasa yang diterima oleh otomata?
A. Bahasa yang dihasilkan oleh otomata.
B. Bahasa yang dapat dikenali oleh otomata.
C. Bahasa yang tidak dapat dikenali oleh otomata.
D. Bahasa yang tidak dapat dihasilkan oleh otomata.
Jawaban:
B. Bahasa yang dapat dikenali oleh otomata.
5. Pernyataan yang benar tentang hubungan antara otomata pushdown (PDA) dan mesin Turing adalah:
A. Setiap PDA dapat diubah menjadi mesin Turing yang setara.
B. Setiap mesin Turing dapat diubah menjadi PDA yang setara.
C. PDA dan mesin Turing memiliki kemampuan yang setara dalam hal pengenalan bahasa.
D. PDA selalu lebih kuat daripada mesin Turing dalam hal kemampuan komputasi.
Jawaban:
C. PDA dan mesin Turing memiliki kemampuan yang setara dalam hal pengenalan bahasa.
6. Otomata yang mampu menerima bahasa dengan pola "a^nb^nc^n" adalah:
A. Otomata DFA
B. Otomata NFA
C. Otomata PDA
D. Otomata Turing
Jawaban:
C. Otomata PDA
7. Apa yang dimaksud dengan otomata berhingga (finite automaton)?
A. Otomata yang memiliki jumlah keadaan terbatas.
B. Otomata yang dapat menerima bahasa berhingga.
C. Otomata yang hanya memiliki alfabet input terbatas.
D. Otomata yang memiliki jumlah fungsi transisi terbatas.
Jawaban:
A. Otomata yang memiliki jumlah keadaan terbatas.
8. Apakah yang dimaksud dengan operasi komposisi dalam teori otomata?
A. Menggabungkan dua otomata menjadi satu otomata baru.
B. Melakukan operasi matematika pada alfabet input otomata.
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.
9. Otomata yang memiliki kemampuan untuk membaca input dari kiri ke kanan dan melakukan perubahan pada sel-selnya adalah:
A. Otomata non-deterministik
B. Mesin Turing
C. Mesin von Neumann
D. Otomata dengan pita tak terbatas
Jawaban:
C. Mesin von Neumann
10. Pernyataan yang benar tentang otomata tak deterministik adalah:
A. Setiap otomata tak deterministik dapat dikonversi menjadi otomata deterministik yang setara.
B. Setiap otomata deterministik dapat dikonversi menjadi otomata tak deterministik yang setara.
C. Otomata tak deterministik dan otomata deterministik tidak dapat saling dikonversi.
D. Otomata tak deterministik selalu lebih kuat daripada otomata deterministik.
Jawaban:
A. Setiap otomata tak deterministik dapat dikonversi menjadi otomata deterministik yang setara.
11. Pernyataan yang benar tentang otomata deterministik terbatas (DFA) adalah:
A. Setiap DFA dapat dikonversi menjadi NFA yang setara.
B. Setiap NFA dapat dikonversi menjadi DFA yang setara.
C. DFA dan NFA memiliki kemampuan yang setara dalam hal pengenalan bahasa.
D. DFA selalu lebih kuat daripada NFA dalam hal kemampuan komputasi.
Jawaban:
C. DFA dan NFA memiliki kemampuan yang setara dalam hal pengenalan bahasa.
12. Pernyataan yang benar tentang hubungan antara otomata pushdown (PDA) dan otomata Turing adalah:
A. Setiap PDA dapat diubah menjadi otomata Turing yang setara.
B. Setiap otomata Turing dapat diubah menjadi PDA yang setara.
C. PDA dan otomata Turing memiliki kemampuan yang setara dalam hal pengenalan bahasa.
D. PDA selalu lebih kuat daripada otomata Turing dalam hal kemampuan komputasi.
Jawaban:
C. PDA dan otomata Turing memiliki kemampuan yang setara dalam hal pengenalan bahasa.
13. Apa yang dimaksud dengan bahasa rekursif 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.
14. Pernyataan yang benar tentang otomata yang mampu mengenali bahasa konteks bebas adalah:
A. Setiap otomata yang mampu mengenali bahasa konteks bebas juga mampu mengenali bahasa reguler.
B. Otomata yang mampu mengenali bahasa konteks bebas hanya dapat memiliki satu keadaan akhir.
C. Otomata yang mampu mengenali bahasa konteks bebas memiliki jumlah keadaan yang terbatas.
D. Setiap bahasa konteks bebas dapat dikenali oleh otomata Turing.
Jawaban:
A. Setiap otomata yang mampu mengenali bahasa konteks bebas juga mampu mengenali bahasa reguler.
15. Apakah yang dimaksud dengan operasi gabungan 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.
16. Pernyataan yang benar tentang hubungan antara otomata non-deterministik (NFA) dan otomata deterministik (DFA) adalah:
A. Setiap NFA dapat dikonversi menjadi DFA yang setara.
B. Setiap DFA dapat dikonversi menjadi NFA yang setara.
C. NFA dan DFA memiliki kemampuan yang setara dalam hal pengenalan bahasa.
D. NFA selalu lebih kuat daripada DFA dalam hal kemampuan komputasi.
Jawaban:
A. Setiap NFA dapat dikonversi menjadi DFA yang setara.