Pertemuan 2 : Derivasi Kalimat dan Penentuan Bahasa

Derivasi Kalimat dan Penentuan Bahasa (Grammar dan Bahasa)

Grammar adalah sebagai kumpulan dari himpunan-himpunan variable, simbol-simbol terminal, symbol awal, yang dibatasi oleh aturan-atuuran produksi. Aturan produksi merupakan pusat dari grammar yang menspesifikasikan bagaimana suatu grammar melakukan transformasi suatu string atau karakter ke bentuk lainnya.

Semua aturan produksi dalam bentuk “α → β” (bisa dibaca Alpha menghasilkan Beta). α adalah simbol-simbol pada ruas kiri aturan prosuksi, sedangkan β merupakan simbol-simbol pada ruas kanan aturan prosuksi. SImbol tersebut dapat berupa symbol terminal (Vt) atau simbol Non-Terminal (Vn).

Simbol Vn adalah simbol yang masih dapat diturunkan, biasanya identic dengan huruf besar (‘A’,’B’,’C’). Sedangkan simbol Vt adalah simbol yang sudah tidak dapat diturunkan lagi, biasanya identic dengan huruf kecil (‘a’,’b’,’c’).

Dengan menerapkan aturan produksi, suatu grammar dapat menghasilkan sejumlah string. Contoh aturan produksinya :

E → T | T+E | T * E

T → a

Derivasi Kalimat dan Penentuan Bahasa

Grammar 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ⁿAaⁿ     (2)

   è aⁿbaⁿ      (3)

L­₁ (G₁) = { aⁿbaⁿ | n ≥ 1}

Contoh tersebut adalah cara untuk menentukan derivasi kalimat terpendek dan juga bentuk umum pada sebuah Grammar yang sudah ditentukan dengan metode substitusi yang disesuaikan pada aturan produksi yang berlaku pada grammar tersebut.

Contoh lainnya :

G₁ dengan Q­₁ = {1. S à aS, 2. S à aB, 3. B à bC, 4. C à aC, 5. C à a}

Jawab :

Derivasi Kalimat Terpendek :

S è aS (1)

   è aaB  (2)

   è aabC  (3)

   è aaba  (5)

 

Derivasi Kalimat umum :

S è aS       (1)

   è aaS   (1)

   è aaaS   (1)

   è aaaaB   (2)

   è aaaabC   (3)

   è aaaabaC   (4)

   è aaaabaaC   (4)

   è aaaabaaa   (5)

   è aⁿba^m

L­₁ (G₁) = { aⁿba^m | m ≥ 1, n > 1}

Demikian artikel ini semoga dapat bermanfaat. Sekian terimakasih.