GRAMMAR DAN BAHASA

Pengertian  Grammar

Grammar adalah sebagai kumpulan dari himpunan-himpunan variabel, simbol-simbol terminal, simbol awal, yang dibatasi oleh aturan-aturan produksi.

Aturan produksi merupakan pusat dari grammar yang menspesifikasikan bagaimana suatu grammar melakukan transformasi suatu string atau karakter ke bentuk lainnya.

—  Semua aturan produksi dinyatakan dalam bentuk “ α à β “ (bisa dibaca α menghasilkan β, atau dibaca α  menurunkan β)
—  α merupakan simbol-simbol pada ruas kiri aturan produksi, sedangkan β merupakan simbol-simbol ruas kanan aturan produksi
—  Simbol-simbol tersebut dapat berupa simbol terminal (Vt) atau simbol NON-Terminal (Vn)/Variabel.
—  Simbol Vn adalah simbol yang masih dapat diturunkan, biasanya identik dengan huruf besar (‘A’,’B’,’C’)
—  Simbol Vt adalah simbol yang sudah tidak dapat diturunkan lagi, biasanya identik dengan huruf kecil (‘a’,’b’,’c’)

Dengan menerapkan aturan produksi, suatu grammar bisa menghasilkan sejumlah string.

Contoh aturan produksi :

E à T | T+E | T * E
T à a

Dari aturan produksi di atas, menghasilkan suatu variabel a atau variabel ekspresi a+a atau a*a

Ø  E à T
T à a

Ø  E à T+E
E à a+T
E à a+a

Ø  E à T*E
E à a*T
E à a*a

Grammar dan Klasifikasi Chomsky

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

            V_T   : himpunan  simbol-simbol  terminal   (atau  himpunan token-token, atau alfabet)

            V_N   : himpunan simbol-simbol non terminal

            S Є V_N   : simbol awal (atau simbol start)

            Q  : himpunan produksi

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

—  Grammar tipe ke-0 : Unrestricted Grammar (UG)

            Ciri : α, β Є (V_T | V_N )*, |α|> 0 atau |α|> |β|

—  Grammar tipe ke-1 : Context Sensitive Grammar (CSG)

            Ciri : α, β Є (V_T | V_N )*, 0 < |α| ≤ |β|

—  Grammar tipe ke-2 : Context Free Grammar (CFG)

            Ciri : α Є V_N , β Є (V_T | V_N )*

—  Grammar tipe ke-3 : Regular Grammar (RG)

            Ciri : α Є V_N , β Є {V_T , V_TV_N} atau α Є V_N , β Є {V_T, V_NV_T }

Derivasi Kalimat dan Penentuan Bahasa

Tentukan bahasa dari masing-masing gramar berikut :

G₁ dengan Q₁   = {1. S ® aAa,  2. A ® aAa,  3. A ® b}.

Jawab :

Derivasi kalimat terpendek :      Derivasi kalimat umum :

S Þ aAa (1)                                        S Þ aAa         (1)

   Þ aba (3)                                            Þ aaAaa      (2)

                                                                             ¼

                                                               Þ aⁿAaⁿ       (2)

                                                               Þ aⁿbaⁿ        (3)

Dari pola kedua kalimat disimpulkan :

L₁ (G₁  ) = { aⁿbaⁿ ½ n ³ 1}

        Berikut ini merupakan contoh soal untuk menetukan apakah produksi-produksi berikut memenuhi aturan Grammar Reguler, Grammer Bebas Konteks, Grammer Konteks Sensitive dan Grammer Unrestricted