Chapter 10: Pushdown Automata (PDA) dan Komputasi Berbasis Stack - Academics

Konsep & Pembahasan Terperinci

1. Hierarki Mesin Berdasarkan Memori Sementara

Jenis Mesin Automata	Karakteristik Memori Sementara	Kelas Bahasa yang Dikenali
Finite Automata (FA)	Tidak mempunyai memori (hanya mengingat via state)	Regular Language
Pushdown Automata (PDA)	Stack terstruktur LIFO (akses terbatas hanya di puncak)	Context-Free Language (CFL)
Turing Machine (TM)	*Pita tak terhingga dengan akses acak (Random Access)*	Recursively Enumerable

2. Definisi Formal 7-Tuple Pushdown Automaton

Suatu PDA didefinisikan secara matematis oleh 7 komponen:

M = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)

Di mana:

$Q$ : Himpunan berhingga state.
$\Sigma$ : Alfabet simbol masukan (input).
$\Gamma$ : Alfabet simbol stack (stack alphabet).
$\delta$ : Fungsi transisi:

\delta : Q \times (\Sigma \cup \{\epsilon\}) \times \Gamma \longrightarrow 2^{Q \times \Gamma^*}

$q_0$ : State awal ( $q_0 \in Q$ ).
$Z_0$ : Simbol awal pengisi dasar stack ( $Z_0 \in \Gamma$ ).
$F$ : Himpunan state final ( $F \subseteq Q$ ).

3. Cara Kerja Transisi dan Instantaneous Description (ID)

Setiap transisi dinyatakan dalam bentuk:

\delta(q, a, X) = \{(p, \alpha)\}

Artinya: Ketika mesin berada di state $q$ , membaca simbol input $a$ (bisa berupa $\epsilon$ ), dan simbol di puncak stack adalah $X$ :

Mesin menghapus (pop) simbol $X$ dari puncak stack.
Mesin berpindah ke state $p$ .
Mesin menambahkan (push) deretan simbol $\alpha \in \Gamma^*$ ke puncak stack (jika $\alpha = \epsilon$ , berarti hanya operasi pop).

Notasi ID (Konfigurasi Sesaat):

\langle q, w, \alpha \rangle

$q$ : State saat ini.
$w$ : Sisa string masukan yang belum dibaca.
$\alpha$ : Isi stack saat ini (simbol paling kiri adalah puncak stack).
Lambang $\vdash$ menyatakan satu langkah transisi, dan $\vdash^*$ menyatakan barisan nol langkah transisi atau lebih.

Studi Kasus 1: PDA Bahasa $L = \{0^n 1^n \mid n \ge 1\}$ (State Final)

Spesifikasi Mesin:

State: $Q = \{q_0, q_1, q_2\}$ , State Awal: $q_0$ , State Final: $F = \{q_2\}$
$\Sigma = \{0, 1\}$ , $\Gamma = \{X, Z_0\}$ , Simbol Awal Stack: $Z_0$

Aturan Transisi:

$\delta(q_0, 0, Z_0) = \{(q_0, XZ_0)\}$ : Simbol 0 pertama $\implies$ push $X$ di atas $Z_0$ .
$\delta(q_0, 0, X) = \{(q_0, XX)\}$ : Simbol 0 berikutnya $\implies$ push $X$ baru.
$\delta(q_0, 1, X) = \{(q_1, \epsilon)\}$ : Simbol 1 pertama $\implies$ pindah ke $q_1$ dan pop satu $X$ .
$\delta(q_1, 1, X) = \{(q_1, \epsilon)\}$ : Simbol 1 berikutnya $\implies$ tetap di $q_1$ dan pop satu $X$ .
$\delta(q_1, \epsilon, Z_0) = \{(q_2, \epsilon)\}$ : Jika seluruh $X$ habis dan $Z_0$ terlihat $\implies$ pop $Z_0$ dan pindah ke state final $q_2$ .

Pelacakan (Tracing) ID untuk String Masukan $w = 0011$ :

\begin{aligned} \langle q_0, 0011, Z_0 \rangle &\vdash \langle q_0, 011, XZ_0 \rangle \quad &&(\text{Baca 0, push X}) \\ &\vdash \langle q_0, 11, XXZ_0 \rangle \quad &&(\text{Baca 0, push X}) \\ &\vdash \langle q_1, 1, XZ_0 \rangle \quad &&(\text{Baca 1, pop X, pindah } q_1) \\ &\vdash \langle q_1, \epsilon, Z_0 \rangle \quad &&(\text{Baca 1, pop X}) \\ &\vdash \langle q_2, \epsilon, \epsilon \rangle \quad &&(\text{Baca } \epsilon\text{, pop } Z_0\text{, pindah } q_2) \end{aligned}

Karena string input habis dibaca dan mesin berhenti di state final $q_2 \in F$ , maka string $0011$ Diterima (Accepted).

Studi Kasus 2: PDA Palindrom Genap $L = \{w w^R\}$ (Stack Kosong)

Spesifikasi Mesin:

Bahasa: $L = \{w w^R \mid w \in \{a, b\}^*\}$ (Contoh: aabbaa)
$Q = \{q_0, q_1\}$ , $F = \emptyset$ (Penerimaan murni berdasarkan stack kosong: $N(M)$ )
$\Sigma = \{a, b\}$ , $\Gamma = \{A, B, Z_0\}$

Mekanisme Kerja:

Di state $q_0$ , setiap simbol $a$ di-push sebagai $A$ , dan simbol $b$ di-push sebagai $B$ .
Tebakan Non-Deterministik: Mesin secara acak "menebak" bahwa ia telah berada di titik tengah palindrom, lalu melakukan transisi $\epsilon$ berpindah ke state $q_1$ tanpa mengubah isi stack.
Di state $q_1$ , mesin mencocokkan input dengan puncak stack: jika input $a$ cocok dengan $A$ , pop $A$ ; jika input $b$ cocok dengan $B$ , pop $B$ .
Terakhir, pop $Z_0$ untuk mengosongkan stack.

Tracing ID Sukses untuk String Masukan $w = \text{aabbaa}$ :

\begin{aligned} \langle q_0, aabbaa, Z_0 \rangle &\vdash \langle q_0, abbaa, AZ_0 \rangle \\ &\vdash \langle q_0, bbaa, AAZ_0 \rangle \\ &\vdash \langle q_0, baa, BAAZ_0 \rangle \\ &\vdash \langle q_1, baa, BAAZ_0 \rangle \quad &&(\text{Tebakan tepat: pindah ke } q_1) \\ &\vdash \langle q_1, aa, AAZ_0 \rangle \quad &&(\text{Cocok b dengan B, pop}) \\ &\vdash \langle q_1, a, AZ_0 \rangle \quad &&(\text{Cocok a dengan A, pop}) \\ &\vdash \langle q_1, \epsilon, Z_0 \rangle \quad &&(\text{Cocok a dengan A, pop}) \\ &\vdash \langle q_1, \epsilon, \epsilon \rangle \quad &&(\text{Pop } Z_0\text{, stack kosong!}) \end{aligned}

String habis dibaca dan stack kosong $\implies$ Diterima (Accepted).

Perbandingan Konsep: State Final $L(M)$ vs Stack Kosong $N(M)$

Parameter	Penerimaan State Final $L(M)$	Penerimaan Stack Kosong $N(M)$
Kriteria Terima	State akhir $p \in F$ saat string habis	Stack benar-benar kosong ( $\epsilon$ ) saat string habis
Kondisi Stack	Boleh masih tersisa simbol di stack	Wajib kosong, tidak memedulikan state akhir
Himpunan $F$	Wajib memiliki $F \ne \emptyset$	Himpunan $F$ diabaikan (bisa $F = \emptyset$ )
Ekuivalensi	Ekuivalen secara komputasi: $L(M) \equiv N(M) \equiv \text{Context-Free Language}$

Latihan Soal & Pembahasan

Level 1 - Basic

Soal 1.1

Sebutkan 7 komponen dalam tuple Pushdown Automata $M = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ .

Soal 1.2

Apa fungsi dari simbol awal stack $Z_0$ ?

Pembahasan/Jawaban

1.1 $Q$ (state), $\Sigma$ (alfabet input), $\Gamma$ (alfabet stack), $\delta$ (fungsi transisi), $q_0$ (state awal), $Z_0$ (simbol awal stack), $F$ (himpunan state final).

1.2 Simbol $Z_0$ berfungsi sebagai penanda dasar stack sehingga operasi pop pada transisi pertama dapat dieksekusi secara sah, serta menjadi penanda bahwa seluruh simbol yang di-push sebelumnya telah berhasil dicocokkan.

Level 2 - Intermediate

Soal 2.1

Sebutkan 3 kondisi yang menyebabkan suatu string input ditolak (rejected) oleh PDA.

Pembahasan/Jawaban

Tiga kondisi penolakan string oleh PDA adalah:

Tidak ada transisi yang valid dari konfigurasi saat ini (stuck / halt).
Input belum selesai dibaca, tetapi stack sudah kosong terlebih dahulu.
Seluruh input telah selesai dibaca, tetapi mesin berada di state yang bukan Final (pada model $L(M)$ ) atau stack belum kosong (pada model $N(M)$ ).

Level 3 - Advanced

Soal 3.1

Mengapa bahasa palindrom genap $\{w w^R\}$ membutuhkan sifat non-deterministik pada PDA dan tidak dapat diselesaikan oleh PDA deterministik (DPDA)?

Pembahasan/Jawaban

Karena pada palindrom tanpa pemisah di tengah (seperti $w w^R$ ), mesin yang membaca deretan simbol tidak memiliki tanda eksplisit kapan bagian paruh pertama ( $w$ ) berakhir dan kapan paruh kedua yang berbalik ( $w^R$ ) dimulai. Mesin harus bebas "menebak" secara non-deterministik kapan saat yang tepat untuk berhenti melakukan operasi push dan mulai melakukan operasi pop pencocokan.

Exam Cheat Sheet

7-Tuple PDA: $M = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ .
Aksi Transisi $\delta(q, a, X)$ : Selalu pop $X$ , lalu push $\alpha$ .
Format ID: $\langle q, x, \alpha \rangle$ dengan relasi transisi $\vdash$ .
Dua Cara Terima:
- $L(M)$ : Berakhir di state final $p \in F$ .
- $N(M)$ : Berakhir dengan stack kosong ( $\epsilon$ ).
Teorema Kesetaraan: $L(M) \equiv N(M) \equiv \text{CFL}$ .

Referensi & Bahan Bacaan

Catatan Penutup

Dengan tuntasnya Bab 10, seluruh peta jalan kurikulum Teori Komputasi dan Bahasa Formal telah berhasil dipetakan secara utuh: dari konsep dasar alfabet dan string, Finite State Automata (DFA, NFA, $\epsilon$ -NFA, Moore, Mealy, Minimisasi), representasi aljabar Regular Expression, hingga perancangan tata bahasa bebas konteks (CFG) dan mesin komputasi bertumpukan stack (Pushdown Automata).