Ekuivalensi CFG ke PDA

Back to IF2224 Teori Bahasa Formal dan Otomata

Ekuivalensi PDA & CFG (Bagian 1: Konversi CFG ke PDA)

Questions/Cues

• Apa hubungan CFG & PDA?

• Apa tujuan konversi CFG $\to$ PDA?

• Apa ide utama di balik konversi ini?

• Bagaimana PDA mensimulasikan derivasi?

• Bagaimana jika top stack Variabel?

• Bagaimana jika top stack Terminal?

• Apa konstruksi formal $P_G$?

• Transisi Tipe 1 ($\delta (q,ϵ,A)$)

• Transisi Tipe 2 ($\delta (q,a,a)$)

• Teorema 6.13

Reference Points

• Slide 12_2023_Equivalence PDA and CFG.pdf (hlm. 2-9)

Hubungan Fundamental CFG & PDA

Teorema inti dari bab ini adalah:

Sebuah bahasa $L$ adalah Context-Free Language (CFL) jika dan hanya jika bahasa $L$ tersebut diterima oleh sebuah Pushdown Automata (PDA).

Ini berarti:

1. Setiap bahasa yang bisa dibangkitkan oleh CFG, pasti bisa dikenali oleh PDA.

2. Setiap bahasa yang bisa dikenali oleh PDA, pasti bisa dibangkitkan oleh CFG.

Karena kita sudah tahu dari materi sebelumnya bahwa PDA (by final state) $\iff$ PDA (by empty stack), maka kita hanya perlu membuktikan:

CFG $\iff$ PDA (by empty stack).

Catatan ini berfokus pada arah pertama: CFG $\to$ PDA.

Tujuan: Konversi CFG $\to$ PDA

Diberikan sebuah CFG $G=(V,T,Q,S)$, kita ingin membuat sebuah PDA $P_G$ yang menerima bahasa yang sama, $L(G)$. Kita akan menggunakan metode acceptance by empty stack.

Tujuannya: Membuktikan bahwa $L(G)=N(P_G)$.

Ide Utama: Simulasi Leftmost Derivation

Ide utamanya adalah membuat PDA yang mensimulasikan leftmost derivation (${\Rightarrow }_{lm}$) dari grammar $G$.

• Stack PDA akan digunakan untuk menyimpan sentential form (bentuk kalimat) dari proses derivasi. Sentential form adalah string yang berisi campuran Variabel dan Terminal.

• Top (puncak) stack akan selalu mewakili simbol paling kiri dari sentential form yang tersisa.

Bagaimana PDA Mensimulasikan Derivasi?

PDA $P_G$ akan bekerja sebagai berikut:

1. Jika top stack adalah Variabel (misal $A$):

   • PDA secara non-deterministik akan memilih salah satu aturan produksi untuk $A$ dari grammar $G$ (misal $A\to \beta$).

   • PDA akan POP $A$ dari stack.

   • PDA akan PUSH $\beta$ (string isi aturan) ke stack.

   • Ini semua terjadi dalam satu transisi spontan (membaca input $ϵ$).

2. Jika top stack adalah Terminal (misal $a$):

   • PDA harus mencocokkan simbol ini dengan string input.

   • PDA akan membaca simbol input berikutnya.

   • Jika simbol input = $a$ (cocok): PDA akan POP $a$ dari stack dan melanjutkan.

   • Jika simbol input $\ne a$ (tidak cocok): Komputasi di jalur non-deterministik ini “mati” (gagal).

Kondisi Penerimaan (Acceptance):

Jika di akhir proses, semua input telah habis dibaca DAN stack menjadi kosong, berarti string input tersebut berhasil diderivasi dari simbol $S$, sehingga string tersebut diterima.

Konstruksi Formal $P_G$

Diberikan $G=(V,T,Q,S)$, kita definisikan PDA $P_G$ sebagai:

$P_G=(\{q\},T,V\cup T,\delta ,q,S)$

• State $Q$: Hanya punya satu state, yaitu $\{q\}$.

• Alfabet Input $\Sigma$: Adalah himpunan terminal $G$, yaitu $T$.

• Alfabet Stack $\Gamma$: Adalah gabungan Variabel dan Terminal $G$, yaitu $V\cup T$.

• Fungsi Transisi $\delta$: Didefinisikan dalam 2 tipe (lihat di bawah).

• Start State $q_0$: Adalah $q$.

• Start Symbol $Z_0$: Adalah start symbol grammar, yaitu $S$.

Transisi Tipe 1: Ekspansi Variabel

Untuk setiap Variabel $A\in V$, kita tambahkan transisi untuk setiap aturan produksinya.

Jika $A\to \beta$ adalah aturan produksi di $G$, maka:

$\delta (q,ϵ,A)=\{(q,\beta )\}$

• Artinya: Di state $q$, tanpa membaca input ($ϵ$), jika top stack adalah $A$, ganti $A$ dengan $\beta$ (POP $A$, PUSH $\beta$). Ini adalah langkah “derivasi”.

Transisi Tipe 2: Pencocokan Terminal

Untuk setiap Terminal $a\in T$, kita tambahkan transisi pencocokan.

$\delta (q,a,a)=\{(q,ϵ)\}$

• Artinya: Di state $q$, jika input adalah $a$ dan top stack adalah $a$, maka POP $a$ dari stack (ganti $a$ dengan $ϵ$) dan lanjut. Ini adalah langkah “pencocokan”.

Teorema 6.13

Jika $P_G$ dibuat dari CFG $G$ dengan metode di atas, maka $N(P_G)=L(G)$.

Ini membuktikan bahwa untuk setiap CFG, ada PDA (by empty stack) yang ekuivalen.

Summary

Setiap Context-Free Grammar (CFG) dapat diubah menjadi Pushdown Automata (PDA) yang ekuivalen yang menerima bahasa yang sama melalui empty stack. PDA ($P_G$) ini bekerja dengan hanya satu state $\{q\}$ dan secara langsung mensimulasikan leftmost derivation dari grammar. PDA menggunakan transisi $ϵ$ untuk mengganti Variabel di top stack dengan isi aturannya (seperti langkah derivasi), dan menggunakan transisi input untuk mencocokkan dan menghapus Terminal di top stack dengan simbol input (langkah pencocokan). String diterima jika seluruh input habis dibaca dan stack menjadi kosong, yang membuktikan bahwa string tersebut dapat diderivasi dari start symbol $S$.

Additional Information

Penting: Urutan PUSH Balik (Reverse Order)

Saat kita bilang “PUSH $\beta$”, ada detail teknis yang sangat penting. Jika aturan produksinya adalah $A\to Y_1{Y}_2\dots Y_k$, stack bekerja dengan basis LIFO (Last-In, First-Out).

Agar $Y_1$ (simbol paling kiri) berada di puncak stack dan diproses terlebih dahulu (sesuai leftmost derivation), kita harus me-PUSH simbol-simbol tersebut dalam urutan terbalik: PUSH $Y_k$, lalu PUSH $Y_{k-1}$, …, lalu PUSH $Y_1$.

Dalam notasi formal $\delta (q,ϵ,A)=\{(q,Y_1{Y}_2\dots Y_k)\}$, string $Y_1\dots Y_k$ secara konvensi berarti $Y_1$ akan berada di puncak.

Contoh: Lacak String “01” pada $G:S\to 0S1\mid ϵ$

1. Grammar $G$:

   • $S\to 0S1$

   • $S\to ϵ$

2. Konstruksi $P_G$:

   • State: $\{q\}$, Start Symbol: $S$

   • $\delta (q,ϵ,S)=\{(q,0S1),(q,ϵ)\}$ (dari 2 aturan $S$)

   • $\delta (q,0,0)=\{(q,ϵ)\}$ (match ‘0’)

   • $\delta (q,1,1)=\{(q,ϵ)\}$ (match ‘1’)

3. Lacak Komputasi (ID) untuk input “01”:

   • (q, 01, S)

   • $⊢(q,01,0S1)$ (Pilih aturan $S\to 0S1$. POP $S$, PUSH $0S1$. Top stack kini ‘0’)

   • $⊢(q,1,S1)$ (Baca input ‘0’, match top stack ‘0’. POP ‘0’. Top stack kini ‘S’)

   • $⊢(q,1,1)$ (Pilih aturan $S\to ϵ$. POP $S$, PUSH $ϵ$. Top stack kini ‘1’)

   • $⊢(q,ϵ,ϵ)$ (Baca input ‘1’, match top stack ‘1’. POP ‘1’. Top stack kini kosong)

4. Hasil: Input habis ($ϵ$), Stack kosong ($ϵ$). String “01” diterima.

Eksplorasi Mandiri

• Coba lacak input “0011” menggunakan $P_G$ di atas.

• Coba lacak input “011” (seharusnya ditolak). Di mana komputasinya “mati”?