UAS TEORI BAHASA DAN AUTOMATA

Finite Automata adalah model komputasi yang digunakan untuk mengenali:

• a) Bahasa yang kontekstual

• b) Bahasa bebas konteks

• c) Bahasa regular

• d) Bahasa bebas kontekstual

Suatu automata dikatakan deterministik (DFA) jika:

• a) Tidak ada transisi epsilon

• b) Setiap simbol input memiliki tepat satu transisi dari setiap keadaan

• c) Mempunyai beberapa keadaan akhir

• d) Memiliki lebih dari satu jalur untuk simbol input yang sama

Regular Expressions digunakan untuk:

• a) Menyusun program komputer

• b) Menggambarkan bahasa regular

• c) Menyusun gramatika bebas konteks

• d) Mendesain Turing Machines

Kleene’s Theorem menyatakan bahwa:

• • a) Setiap bahasa bebas konteks dapat digambarkan dengan automata

• b) Setiap bahasa regular dapat digambarkan dengan DFA

• c) Setiap bahasa regular dapat digambarkan dengan regular expression

• d) Setiap Turing Machine dapat digambarkan dengan PDA

Pumping Lemma digunakan untuk:

• a) Membuktikan bahasa kontekstual

• b) Membuktikan bahasa regular

• c) Membuktikan bahasa bebas konteks

• d) Mendesain Turing Machine

Context-Free Grammar (CFG) terdiri dari:

• a) Terminal, non-terminal, simbol awal, dan aturan produksi

• b) Hanya terminal dan non-termina

• • c) Simbol awal dan aturan produksi

• d) Simbol terminal dan aturan produksi

Pushdown Automata (PDA) berbeda dengan Finite Automata karena:

• a) PDA memiliki memori berbentuk stack

• b) PDA dapat mengenali bahasa regular

• c) PDA tidak memiliki keadaan akhir

• d) PDA menggunakan tabel transisi

Turing Machine dianggap lebih kuat dibandingkan PDA karena:

• • a) Turing Machine memiliki memori tak terbatas

• b) Turing Machine lebih cepat

• c) Turing Machine dapat menjalankan semua program komputer

• d) Turing Machine menggunakan dua stack

The Halting Problem adalah masalah yang menyatakan bahwa:

• a) Tidak ada cara untuk menentukan apakah suatu Turing Machine akan berhenti atau berjalan selamanya

• b) Semua Turing Machine akan berhenti pada input tertentu

• c) Setiap masalah dapat diselesaikan oleh Turing Machine

• d) Turing Machine dapat memecahkan masalah matematika

Kelas kompleksitas P dan NP merujuk pada:

• a) Waktu komputasi yang diperlukan oleh Turing Machine

• b) Kelas bahasa yang dapat dikenali oleh DFA

• c) Kelas bahasa yang dapat dikenali oleh PDA

• d) Memori yang diperlukan oleh Turing Machine