Soal Pilihan Ganda PDA (sesi 11)

Apa yang dimaksud dengan Push Down Automata (PDA)?

• Mesin dengan input tape dan finite control

• Finite Automaton yang memiliki stack sebagai tambahan memori

• Model matematika tanpa stack

• Mesin yang menerima bahasa regular saja

Komponen utama PDA, kecuali:

• Finite control

• Input tape

• Stack

• Printer output

Fungsi transisi PDA didefinisikan sebagai:

• Q × Σ × Γ → Q × Σ

• Q × Σ × Γ → Subset Q × Γ*

• Q × Σ → Q

• Σ × Γ → Q

PDA menerima bahasa dengan cara:

• Hanya mencapai state final

• Stack kosong

• State final atau stack kosong

• Menghitung panjang string input

Simbol awal pada stack PDA biasanya disebut:

• Z0

• q0

• δ

• ��

Bahasa yang dikenali oleh PDA adalah:

• Bahasa regular

• Bahasa konteks bebas

• Bahasa sensitif konteks

• Bahasa numerik

Fungsi PUSH pada PDA adalah untuk:

• Menghapus simbol dari stack

• Menambah simbol ke stack

• Memindahkan input

• Mengubah state tanpa operasi stack

Fungsi POP pada PDA digunakan untuk:

• Menambah simbol pada stack

• Menghapus simbol dari atas stack

• Menerima input baru

• Membandingkan state

PDA biasanya memiliki:

• Satu state tanpa stack

• Banyak state dan stack

• Stack tanpa state

• Hanya input tape tanpa stack

Berikut ini bukan komponen dari PDA:

• Q (set of states)

• Σ (input alphabet)

• F (set of final states)

• Output tape