coba2

Nama

NIM

Kelas

• A
• B
• C
• D
• E

Jika M adalah sebuah PDA, maka Anda dapat membuat sebuah PDA yang baru yg menerima hasil komplemen dari L(M) dengan cari mengubah final state yang dimilikinya menjadi non final dan sebaliknya dari non final menjadi final

• Benar
• Salah

Sebuah Push Down Automata dapat melakukan komputasi yang Turing Machine tidak dapat melakukannya

• Benar
• Salah

Sebuah Turing Machine dapat melakukan komputasi apapun yang PC dapat lakukan, namun mungkin dengan waktu proses yang lebih lama

• Benar
• Salah

Halting problem termasuk dalam decidable problem

• Benar
• Salah

Semua masalah memiliki sebuah algoritma sebagai solusi penyelesaiannya

• Benar
• Salah

Seandainya ada 2 languange L1 dan L2, dimana L1 adalah Context Free language dan L2 adalah Recursively Enumerable. Manakah pernyatan berikut yang benar:

• Hanya 1
• Hanya 3
• Hanya 3 dan 4
• Hanya 1 dan 4

Semua language adalah decidable

• Benar
• Salah