TBO 

GRAMMAR DAN BAHASA

Dalam pembicaraan grammar, anggota alfabet dinamakan simbol terminal atau token. 

• Kalimat adalah deretan hingga simbol-simbol terminal. 

• Bahasa adalah himpunan kalimat-kalimat dan anggota bahasa bisa tak hingga kalimat. 

• Simbol-simbol berikut adalah simbol terminal: 

• huruf kecil awal alfabet, misalnya: 𝑎, 𝑏, 𝑐 

• simbol operator, misalnya: +, −, dan × 

• simbol tanda baca, misalnya: (, ), dan ; 

• string yang tercetak tebal, misalnya: 𝒊𝒇, 𝒕𝒉𝒆𝒏, dan 𝒆𝒍𝒔𝒆. 

• Simbol-simbol berikut adalah simbol non terminal: 

• huruf besar awal alfabet, misalnya: 𝐴,𝐵, 𝐶; 

• huruf S sebagai simbol awal; 

• string yang tercetak miring, misalnya: expr dan stmt. 

• Huruf besar akhir alfabet melambangkan simbol terminal atau non terminal, misalnya: 𝑋, 𝑌, 𝑍. 

• Huruf kecil akhir alfabet melambangkan string yang tersusun atas simbol-simbol terminal, misalnya: 𝑥, 𝑦, 𝑧.

• Huruf yunani melambangkan string yang tersusun atas simbol-simbol terminal atau simbol-simbol non terminal atau campuran keduanya, misalnya: 𝛼, 𝛽, dan 𝛾.

 • Sebuah produksi dilambangkan sebagai 𝛼 → 𝛽, artinya: dalam sebuah derivasi dapat dilakukan penggantian simbol 𝛼 dengan simbol 𝛽. 

• Simbol α dalam produksi berbentuk 𝛼 → 𝛽 disebut ruas kiri produksi sedangkan simbol 𝛽 disebut ruas kanan produksi.

Grammar dan Klasifikasi CHOMSKY

Derivasi adalah proses pembentukan sebuah kalimat atau sentensial. Sebuah derivasi dilambangkan sebagai: 𝛼 ⇒ 𝛽. 

Sentensial adalah string yang tersusun atas simbol-simbol terminal atau simbol-simbol non terminal atau campuran keduanya. 

• Kalimat adalah string yang tersusun atas simbol-simbol terminal dan kalimat adalah kasus khusus dari sentensial. 

• Pengertian terminal (terminate = berakhir) dicapai, jika sentensial yang dihasilkan adalah sebuah kalimat yang tersusun atas simbol-simbol terminal itu. 

• Pengertian non terminal (not terminate = belum/tidak berakhir), jika sentensial yang dihasilkan masih mengandung simbol non terminal. 

• Grammar G didefinisikan sebagai pasangan 4 tuple: VT , VN , S, dan Q, dan dituliskan sebagai G(VT , VN , S, Q), dimana: 

𝑽𝑻         : himpunan simbol-simbol terminal (atau himpunan token – token, atau alfabet) 

𝑽𝑵        : himpunan simbol-simbol non terminal 

𝑺 ∈ 𝑽𝑵 : simbol awal (atau simbol start) 

𝑸          : himpunan produksi

DERIVASI

proses pembentukan sebuah kalimat atau sentensial. Sebuah derivasi dilambangkan sebagai: 𝛼 ⇒ 𝛽.

Contoh. 

Tentukan derivasi kalimat dari grammar Q berikut. G dengan Q = {1. S → aAa, 2. A → aAa, 3. A → b}.

Jawab. 

Derivasi kalimat terpendek: S ⇒ aAa (1) ⇒ aba (3)

Derivasi kalimat umum: 

S ⇒ aAa (1) 

⇒ aaAaa (2) 

⇒ ...

 ⇒ a nAan (2) 

⇒ a nban (3) 

Kesimpulan: L(G) = {a^nba^n | n ≥ 1}

Berdasarkan komposisi bentuk ruas kiri dan ruas kanan produksinya (𝛼 → 𝛽), Noam Chomsky mengklasifikasikan 4 tipe grammar:

1. Grammar tipe ke-0: Unrestricted Grammar (UG)

Ciri: 𝛼, 𝛽 ∈ 𝑉𝑇 𝑉𝑁 ) ∗ ,|𝛼| > 0

Aturan: Tidak ada batasan pada aturan produksi

Contoh: 

Abc → De 

SAac → Abc

2. Grammar tipe ke-1: Context Sensitive Grammar (CSG)

Ciri: 𝛼, 𝛽 ∈ (𝑉𝑇 | 𝑉𝑁 ) ∗, 0 < | 𝛼 | ≤ | 𝛽 |

Aturan: Panjang string ruas kiri harus < (lebih kecil) atau = (sama dengan) ruas kanan  

Contoh:  

Ab → DeF 

CD → eF

3. Grammar tipe ke-2: Contex Free Grammar (CFG)

Ciri: 𝛼 ∈ 𝑉𝑁 , 𝛽 ∈ (𝑉𝑇 | 𝑉𝑁 ) ∗

Aturan: Ruas kiri haruslah tepat satu simbol variabel, yaitu simbol non terminal 

Contoh:  

Ab → DeF 

CD → eF

4. Grammar tipe ke-3: Regular Grammar (RG)

Ciri: 𝛼 ∈ 𝑉𝑁 , 𝛽 ∈ {𝑉𝑇 , 𝑉𝑇𝑉𝑁 }, atau 𝛼 ∈ 𝑉𝑁 , 𝛽 ∈ {𝑉𝑇 , 𝑉𝑁𝑉𝑇 }

Aturan: Ruas kanan hanya memiliki maksimal satu simbol non terminal 

Contoh:  

A → e                                 A → efgH 

A → efg                             C → D