Teori Bahasa dan Automata bagian 1 - UNNES ILMU KOMPUTER

Bahasa yang mengenali string dengan pola a^n b^n termasuk dalam kategori:

• Bahasa Reguler
• Bahasa Bebas-Konteks
• Bahasa Sensitif-Konteks
• Bahasa Tak Terbatas
• Bahasa Turing

Manakah dari produksi berikut yang valid dalam bahasa tak terbatas (unrestricted)?

• A → ε
• A → B
• A → abC
• aA → ab
• Semua jawaban benar

Mesin pengenal yang digunakan untuk bahasa sensitif-konteks adalah:

• Finite Automaton
• Pushdown Automaton
• Linear Bounded Automaton
• Turing Machine
• Non-deterministic Finite Automaton

Manakah dari produksi berikut yang merupakan produksi bahasa reguler?

• A → Ba
• A → abC
• A → aB
• A → Aab
• A → ε

Aturan produksi mana yang sesuai dengan tata bahasa sensitif-konteks?

• A → aB
• AB → CD
• A → B
• aA → ab
• A → ε

Bahasa dengan pola a^n b^n c^n termasuk dalam kategori:

• Bahasa Bebas-Konteks
• Bahasa Sensitif-Konteks
• Bahasa Reguler
• Bahasa Tak Terbatas
• Bahasa Turing

Bahasa yang bisa dikenali oleh Pushdown Automaton adalah:

• Bahasa Bebas-Konteks
• Bahasa Reguler
• Bahasa Sensitif-Konteks
• Bahasa Tak Terbatas
• Bahasa Rekursif

Di bawah ini, mana yang bukan karakteristik bahasa reguler?

• Tidak bisa menggunakan epsilon
• Menggunakan finite automaton
• Mengandung aturan produksi berbentuk A → a atau A → aB
• Mengizinkan produksi berbentuk A → A
• Tidak mengenali konteks dalam string

Bahasa dengan pola a^n b^n c^n hanya bisa dikenali oleh:

• Turing Machine
• Pushdown Automaton
• Finite Automaton
• Linear Bounded Automaton
• Non-deterministic Pushdown Automaton

Bahasa tak terbatas (unrestricted) mengizinkan aturan produksi berikut:

• A → aB
• A → B
• A → ε
• aA → ab
• Semua jawaban benar