Nama : Adrianus V Wasonono
Kelas : B
NIM : 18110478
Kelas : B
NIM : 18110478
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}
Tidak ada komentar:
Posting Komentar