tugas 1 teknik kompilasi

CONTOH KLASIFIKASI GRAMMER MENURUT COMSKY

Contoh klasifikasi grammer menurut comsky
Maret 27, 2020
Klasifikasi Chomsky
Grammar G didefinisikan sebagai pasangan 4 tuple : V, V, S, dan Q, dan dituliskan sebagai G(V, V, S, Q), dimana :
V         : himpunan  simbol-simbol  terminal  (atau  himpunan  token -token, atau alfabet)
V        : himpunan simbol-simbol non terminal
S Î V : simbol awal (atau simbol start)
Q            : himpunan produksi

Berdasarkan komposisi bentuk ruas kiri dan ruas kanan produksinya (a ® b), Noam Chomsky mengklasifikasikan 4 tipe grammar :
1.      Grammar tipe ke-0 : Unrestricted Grammar (UG)
Ciri : a, b Î (V½V)*, ïaï> 0
Tidak ada batasan pada aturan produksi
Contoh:
Abc → De
2.      Grammar tipe ke-1 : Context Sensitive Grammar (CSG)
Ciri : a, b Î (V½V)*, 0 < ïaï £ ïbï
Panjang string ruas kiri harus < (lebih kecil) atau = (sama dengan) ruas kanan
Contoh:
Ab → DeF
CD → eF
3.      Grammar tipe ke-2 : Context Free Grammar (CFG)
Ciri : a Î V, b Î (V½V)*
Ruas kiri haruslah tepat satu symbol variabel, yaitu simbol non terminal
Contoh :
B → CDeFg
D → BcDe
4.      Grammar tipe ke-3 : Regular Grammar (RG)
Ciri : a Î V, b Î {V, VV} atau a Î V, b Î {V, VV}
Ruas kanan hanya memiliki maksimal satu symbol non terminal
Contoh
·         Mengingat ketentuan simbol-simbol (hal. 3 no. 4 dan 5), ciri-ciri RG sering dituliskan sebagai : a Î V, b Î {a, bC} atau a Î V, b Î {a, Bc}
A → e
A → efg
A → efgH
C → D
Tipe sebuah grammar (atau bahasa) ditentukan dengan aturan sebagai berikut :
A language is said to be type-i (i = 0, 1, 2, 3) language if it can be specified by a type-i grammar but can’t be specified any type-(i+1) grammar.
Gambar 1. Hirarki Chomsky
Contoh Analisa Penentuan Type Grammar
Grammar G dengan Q = {S ® aB, B ® bB, B ® b}.
Ruas kiri semua produksinya terdiri dari sebuah V maka G kemungkinan tipe CFG atau RG. Selanjutnya karena semua ruas kanannya terdiri dari sebuah V atau string VV maka G adalah RG.
Grammar G dengan Q = {S ® Ba, B ® Bb, B ® b}.
Ruas kiri semua produksinya terdiri dari sebuah V maka G kemungkinan tipe CFG atau RG. Selanjutnya karena semua ruas kanannya terdiri dari sebuah V atau string VV maka G adalah RG.
Grammar G dengan Q = {S ® Ba, B ® bB, B ® b}.
Ruas kiri semua produksinya terdiri dari sebuah V maka G kemungkinan tipe CFG atau RG. Selanjutnya karena ruas kanannya mengandung string VV (yaitu bB) dan juga string VV (Ba) maka G bukan RG, dengan kata lain G adalah CFG.
Grammar G dengan Q = {S ® aAb, B ® aB}.
Ruas kiri semua produksinya terdiri dari sebuah V 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}.
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}.
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 kananya (yaitu SAc) maka G adalah UG.
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)
¼
Þ aAa     (2)
Þ aba       (3)
Dari pola kedua kalimat disimpulkan : L(G) = { aba½ n ³ 1}

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)                                              Þ aS                   (1)
Þ aB                       (2)
Þ abC                   (3)
Þ abaC                 (4)
¼
Þ abaC           (4)
Þ aba                (5)
Dari pola kedua kalimat disimpulkan : L (G) = { aba½ n ³ 1, m ³ 1}

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) = { abc½ n ³ 1}