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 G didefinisikan sebagai pasangan 4 tuple : VT , VN , S, dan Q, dan dituliskan sebagai G(V_T , V_N, S, Q), dimana :

1. V_T   : himpunan  simbol-simbol  terminal   (atau  himpunan token-token, atau alfabet)
2. V_N   : himpunan simbol-simbol non terminal
3. S Є V_N   : simbol awal (atau simbol start)
4. 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 }

CONTOH ANALISA PENETUAN TYPE GRAMMAR

Grammar G₁  dengan Q₁  = {S → aB,      B → bB, B → b}.

Jawab :

Ruas kiri semua produksinya terdiri dari sebuah V_N  maka G₁  kemungkinan tipe CFG atau RG.

Selanjutnya karena semua ruas  kanannya terdiri dari sebuah V_T  atau string V_T V_N  maka G₁  adalah RG

Grammar G₂  dengan Q₂  = {S → Ba,      B → Bb, B → b}.

Jawab :

Ruas kiri semua produksinya terdiri dari sebuah V_N maka G₂  kemungkinan tipe CFG atau RG.

Selanjutnya karena semua ruas  kanannya terdiri dari sebuah V_T  atau string V_NV_T  maka G₂  adalah RG

Grammar G₃  dengan Q₃  = {S → Ba,      B → bB, B → b}.

Jawab :

Ruas kiri semua produksinya terdiri dari sebuah V_N maka G₃  kemungkinan tipe CFG atau RG.

Selanjutnya karena ruas kanannya mengandung string V_T V_N  (yaitu bB) dan juga string V_NV_T  (Ba) maka G₃  bukan RG, dengan kata lain G₃  adalah CFG

Grammar G₄ dengan Q₄ = {S → aAb, B → aB}.

Jawab :

Ruas kiri semua produksinya terdiri dari sebuah V_N  maka G₄  kemungkinan tipe CFG atau RG.

Selanjutnya karena ruas kanannya mengandung string yang panjangnya lebih dari 2 (yaitu aAb) maka G₄  bukan RG, dengan kata lain G₄  adalah CFG

Grammar G₅  dengan Q₅  = {S → aA,      S → aB, aAb → aBCb}

Jawab :

Ruas kirinya mengandung string yang panjangnya lebih dari 1 (yaitu aAb) maka G₅ kemungkinan tipe CSG atau UG.

Selanjutnya karena semua ruas kirinya lebih pendek atau sama dengan ruas kananya maka G₅  adalah CSG

Grammar G₅  dengan Q₅  = {S → aA,      S → aB, aAb → aBCb}.

Jawab :

Ruas kirinya mengandung string yang panjangnya lebih dari 1 (yaitu aAb) maka G₅ kemungkinan tipe CSG atau UG.

Selanjutnya karena semua ruas kirinya lebih pendek atau sama dengan ruas kananya maka G₅  adalah CSG

Grammar G₆  dengan Q₆ = {aS → ab,  SAc → bc}.

Jawab :

Ruas kirinya mengandung string yang panjangnya lebih dari 1 maka G₆  kemungkinan tipe CSG atau UG.

Selanjutnya karena terdapat ruas kirinya yang lebih panjang daripada ruas kanannya (yaitu SAc) maka G₆  adalah UG

DERIVASI KALIMAT DAN PENENTUAN BAHASA

1. 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}

2. Tentukan bahasa dari masing-masing gramar berikut :

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

Jawab :

Derivasi kalimat terpendek :  Derivasi kalimat umum :

S Þ aB            (2)                    S Þ aS                                     (1)

   Þ abC         (3)                        ¼

   Þ aba          (5)                       Þ a^n-1S                     (1)    

                                                   Þ aⁿ B                      (2)

                                                   Þ aⁿbC                    (3)

                                                   Þ aⁿbaC                   (4)

                                                    ¼

                                                    Þ aⁿba^m-1C              (4)

                                                    Þ aⁿ ba^m                 (5)

Dari pola kedua kalimat disimpulkan :

L₂  (G₂ ) = { aⁿ ba^m ½ n ³ 1, m ³ 1}

3. Tentukan bahasa dari masing-masing gramar berikut :

G₃ dengan Q₃  = {1. S ® aSBC,  2. S ® abC,  3. bB ® bb,  4. bC ® bc,         5. CB ® BC,  6. cC ® cc}.

Jawab :

Derivasi kalimat terpendek 1:                        Derivasi kalimat terpendek 3 :

S Þ abC          (2)                                S Þ aSBC        (1)

   Þ abc          (4)                                   Þ aaSBCBC (1)

Derivasi kalimat terpendek 2 :                          Þ aaabCBCBC         (2)

S Þ aSBC        (1)                                   Þ aaabBCCBC         (5)

   Þ aabCBC   (2)                                   Þ aaabBCBCC         (5)

   Þ aabBCC   (5)                                   Þ aaabBBCCC         (5)

   Þ aabbCC    (3)                                   Þ aaabbBCCC         (3)

   Þ aabbcC    (4)                                   Þ aaabbbCCC         (3)

   Þ aabbcc     (6)                                   Þ aaabbbcCC          (4)

                                                               Þ aaabbbccC          (6)

                                                               Þ aaabbbccc           (6)

Dari pola ketiga kalimat disimpulkan : L ₃ (G₃ ) = { aⁿbⁿ cⁿ ½ n ³ 1}

MENENTUKAN GRAMMAR SEBUAH BAHASA

1.Tentukan sebuah grammar regular untuk bahasa L₁ = { aⁿ | n ≥ 1}

—  Jawab :

            Q₁ (L₁ ) = {S → aS | a}
S à a atau
S à aS à aa atau
S à aS à aaS à aaa

2. Tentukan sebuah grammar bebas konteks untuk bahasa : 

            L₂ : himpunan bilangan bulat non negatif ganjil

—  Jawab :

            Langkah kunci : digit terakhir bilangan harus ganjil. 

            Buat dua buah himpunan bilangan terpisah : genap (G) dan ganjil (J)

            Q₂(L₂ ) = {S → J|GS|JS,  G → 0|2|4|6|8,           J → 1|3|5|7|9}

3.  Tentukan sebuah grammar bebas konteks untuk bahasa : 

            L₂ : himpunan bilangan bulat non negatif ganjil

—  Jawab :

            Langkah kunci : digit terakhir bilangan harus ganjil. 

            Buat dua buah himpunan bilangan terpisah : genap (G) dan ganjil (J)

            Q₂(L₂ ) = {S → J|GS|JS,  G → 0|2|4|6|8,           J → 1|3|5|7|9}

4. Tentukan sebuah gramar bebas konteks untuk bahasa :

            L₃  = himpunan semua identifier yang sah menurut bahasa pemrograman Pascal

            dengan batasan : terdiri dari simbol huruf kecil dan angka, panjang identifier boleh lebih dari 8 karakter

—  Jawab :

            Langkah kunci : karakter pertama identifier harus huruf. 

            Buat dua buah himpunan bilangan terpisah : huruf (H) dan angka (A)

            Q₃ (L₃ ) = {S → H|HT, T → AT|HT|H|A,   H → a|b|c|…,  A → 0|1|2|…}

—  Contoh :

—  G₁ :  V_T = {I,  Love, Miss, You}, V = {S,A,B,C}, P = {S ® ABC, A® I, B® Love | Miss, C® You}

—  S Þ ABC

—     Þ I loveYou

 L(G₁)={I love You, I Miss You}

5. Tentukan apakah produksi-produksi berikut memenuhi aturan grammar Reguler :

A à b
B à bdB
B à C
B à bC
B à Ad
B à bcdef
A à aSa
A à aSS
Ad à dB

6. Tentukan apakah produksi-produksi berikut memenuhi aturan grammar Bebas Konteks :

A à aSa
B à Ace
B à ab

B à bcdef
B à bcdefG
B à aSS
A à BCDEF
A à AAAA
Ad à dB

7.  Tentukan apakah produksi-produksi berikut memenuhi aturan grammar Konteks Sensitive :

A à bcdefG
B à aSa
B à aSS
B à BCDEF
Ad à dB
ad à b
abC à DE
abcDef à ghijkl
AB à cde
AAA à BBB

8. Tentukan apakah produksi-produksi berikut memenuhi aturan grammar Unrestricted :

ad à b
abC à DE
AB à cde
ABCDEFG à h
bA à CDEFG

GRAMMAR DAN KLASIFIKASI CHOMSKY LANJT.

Grammar G didefinisikan sebagai pasangan 4 tuple : V_T , V_N , 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

HIRARKI CHOMSKY