Chapter 9: Context-Free Grammar (CFG) dan Tata Bahasa Bebas Konteks - Academics

Konsep & Pembahasan Terperinci

1. Batasan DFA dan Kebutuhan Memori Rekursif

Kelemahan DFA:

Pada bahasa $\{a^i b^j \mid i, j \ge 0\}$ , jumlah huruf $a$ dan $b$ bebas dan tidak saling bergantung, sehingga cukup dikenali oleh DFA (ekspresi $a^*b^*$ ).

Namun pada bahasa $\{a^n b^n \mid n \ge 0\}$ , jumlah huruf $a$ harus persis sama dengan jumlah huruf $b$ . Untuk memverifikasinya, mesin harus "menghitung" berapa banyak $a$ yang telah dibaca. Karena $n$ bisa bernilai berapa pun hingga tak hingga, DFA yang memorinya terbatas (fixed state) pasti gagal.
Solusi CFG:

CFG mendefinisikan aturan secara rekursif:

S \longrightarrow aSb \mid \epsilon

Setiap kali simbol terminal $a$ ditambahkan di sisi kiri, terminal $b$ otomatis ditambahkan di sisi kanan secara berpasangan.

2. Definisi Formal Context-Free Grammar (4-Tuple)

Suatu Context-Free Grammar didefinisikan sebagai 4-tuple:

G = (V, T, P, S)

Di mana:

$V$ : Himpunan berhingga simbol variabel / non-terminal. Simbol ini mewakili kategori sintaksis yang didefinisikan secara rekursif (contoh: $S, A, B$ , atau sentence).
$T$ : Himpunan berhingga simbol terminal ( $T = \Sigma$ ). Simbol ini adalah karakter alfabet dasar yang muncul dalam string akhir kalimat (contoh: $a, b$ , dog, runs). $V \cap T = \emptyset$ .
$S$ : Simbol awal (start symbol), di mana $S \in V$ .
$P$ : Himpunan berhingga aturan produksi (production rules), berbentuk:

A \longrightarrow \alpha

di mana $A \in V$ dan $\alpha \in (V \cup T)^*$ .

Studi Kasus & Derivasi Grammar

1. Grammar Bahasa Alami (Natural Language)

Aturan Produksi:

$\text{sentence} \to \text{noun\_phrase } \text{predicate}$
$\text{noun\_phrase} \to \text{article } \text{noun}$
$\text{predicate} \to \text{verb}$
$\text{article} \to a \mid the$
$\text{noun} \to cat \mid dog$
$\text{verb} \to runs \mid walks$

Pelacakan Derivasi Kalimat `"the dog walks"`:

\begin{aligned} \text{sentence} &\Longrightarrow \text{noun\_phrase } \text{predicate} \\ &\Longrightarrow \text{noun\_phrase } \text{verb} \\ &\Longrightarrow \text{article } \text{noun } \text{verb} \\ &\Longrightarrow the \text{ noun } \text{verb} \\ &\Longrightarrow the \text{ dog } \text{verb} \\ &\Longrightarrow the \text{ dog walks} \end{aligned}

2. CFG Bahasa Bersarang $L = \{a^n b^n\}$

Aturan Produksi:

S \longrightarrow aSb \mid \epsilon

Pelacakan Derivasi Kalimat `"aaabbb"`:

S \Longrightarrow aSb \Longrightarrow aaSbb \Longrightarrow aaaSbbb \Longrightarrow aaa(\epsilon)bbb = aaabbb

Notasi ringkas (multi-step derivation):

S \Longrightarrow^* aaabbb

3. Konversi Ekspresi Reguler $(a+b)^*$ ke CFG

Ekspresi reguler $(a+b)^*$ dapat diubah ke aturan produksi CFG sebagai berikut:

S \longrightarrow aS \mid bS \mid a \mid b \mid \epsilon

Aturan ini memungkinkan pembangkitan sembarang barisan simbol $a$ dan $b$ dengan panjang berapapun.

Latihan Soal & Pembahasan

Level 1 - Basic

Soal 1.1

Sebutkan 4 komponen tuple formal dari CFG $G = (V, T, P, S)$ .

Soal 1.2

Apa perbedaan mendasar antara simbol variabel ( $V$ ) dan simbol terminal ( $T$ )?

Pembahasan/Jawaban

1.1 $V$ (variabel non-terminal), $T$ (terminal alfabet), $P$ (aturan produksi), dan $S$ (simbol awal start).

1.2 Simbol variabel ( $V$ ) adalah entitas sintaksis perantara yang masih dapat diturunkan/digantikan melalui aturan produksi. Simbol terminal ( $T$ ) adalah karakter literal akhir bahasa yang tidak dapat diturunkan lagi.

Level 2 - Intermediate

Soal 2.1

Rancang aturan produksi CFG untuk bahasa palindrom berpanjang genap di atas alfabet $\Sigma = \{0, 1\}$ yaitu $L = \{w w^R \mid w \in \{0, 1\}^*\}$ .

Pembahasan/Jawaban

Aturan produksi harus menambahkan simbol yang sama di sisi kiri dan kanan secara simetris:

S \longrightarrow 0S0 \mid 1S1 \mid \epsilon

Contoh derivasi string $0110$: $S \Rightarrow 0S0 \Rightarrow 0(1S1)0 \Rightarrow 01(\epsilon)10 = 0110$ .

Level 3 - Advanced

Soal 3.1

Jelaskan mengapa tahap analisis sintaktik pada kompilator bahasa pemrograman wajib menggunakan CFG dan bukan Finite Automata.

Pembahasan/Jawaban

Struktur kode program memiliki sifat bersarang (nested hierarchies) yang sangat dalam, seperti ekspresi matematika berpasangan kurung (A + (B * (C - D))), blok percabangan if ... else bersarang, dan pemanggilan fungsi rekursif. Finite Automata tidak memiliki mekanisme memori untuk memverifikasi kecocokan pasangan buka-tutup yang bertingkat banyak tersebut. CFG mampu memodelkan relasi bersarang ini secara alami melalui aturan produksi rekursif yang diproses menjadi pohon sintaks (parse tree).

Exam Cheat Sheet

4-Tuple CFG: $G = (V, T, P, S)$ .
Format Produksi: $A \to \alpha$ di mana $A \in V$ dan $\alpha \in (V \cup T)^*$ .
Bahasa Non-Reguler Khas: $\{a^n b^n \mid n \ge 0\}$ dan palindrom $\{w w^R\}$ .
Notasi Penurunan: $\Rightarrow$ (satu langkah derivasi), $\Rightarrow^*$ (banyak langkah derivasi).
Peran di Compiler: Menjadi basis parser pada tahap Analisis Sintaktik.

Referensi & Bahan Bacaan

Catatan Penutup

Bab 9 menyajikan tata bahasa bebas konteks secara deklaratif. Namun, mesin komputasi apa yang bertugas mengeksekusi dan memvalidasi bahasa CFL ini? Jawabannya akan dibahas pada bab penutup, Chapter 10: Pushdown Automata (PDA).