GRAMMAR DAN BAHASA
Konsep Dasar
- Anggota alfabet dinamakan simbol terminal.
- Kalimat adalah deretan hingga simbol-simbol terminal.
- Bahasa adalah himpunan kalimat-kalimat. Anggota bahasa bisa tak hingga kalimat.
- Simbol-simbol berikut adalah simbol terminal :
ü huruf kecil, misalnya : a, b, c, 0, 1, ..
ü simbol operator, misalnya : +, -, dan ´
ü simbol tanda baca, misalnya : (, ), dan ;
ü string yang tercetak tebal, misalnya : if, then, dan else.
- Simbol-simbol berikut adalah simbol non terminal /Variabel :
ü huruf besar, misalnya : A, B, C
ü huruf S sebagai simbol awal
ü string yang tercetak miring, misalnya : expr
- Huruf yunani melambangkan string yang tersusun atas simbol-simbol terminal atau simbol-simbol non terminal atau campuran keduanya, misalnya : a, b, dan g.
- Sebuah produksi dilambangkan sebagai a ® b, artinya : dalam sebuah derivasi dapat dilakukan penggantian simbol a dengan simbol b.
- Derivasi adalah proses pembentukan sebuah kalimat atau sentensial. Sebuah derivasi dilambangkan sebagai : a Þ b.
- Sentensial adalah string yang tersusun atas simbol-simbol terminal atau simbol-simbol non terminal atau campuran keduanya.
- Kalimat adalah string yang tersusun atas simbol-simbol terminal. Kalimat adalah merupakan sentensial, sebaliknya belum tentu.
Grammar :
Grammar G didefinisikan sebagai pasangan 4 tuple : V
, V
, S, dan P, dan dituliskan sebagai G(V, V, S, P), dimana :
, V, S, dan P, dan dituliskan sebagai G(V, V, S, P), dimana :V : himpunan simbol-simbol terminal (alfabet) àkamus
: himpunan simbol-simbol terminal (alfabet) àkamusV : himpunan simbol-simbol non terminal
: himpunan simbol-simbol non terminalSÎV : simbol awal (atau simbol start)
: simbol awal (atau simbol start)P : himpunan produksi
Contoh :
1. G1 : VT = {I, Love, Miss, You}, V = {S,A,B,C},
= {S,A,B,C}, P = {S ® ABC, A® I, B® Love | Miss, C® You}
S Þ ABC
Þ IloveYou
L(G1)={IloveYou, IMissYou}
2. . G2 : VT = {a}, V = {S}, P = {S ® aS½a}
= {S}, P = {S ® aS½a} S Þ aS
Þ aaS
Þ aaa L(G2) ={an ½ n ≥ 1}
L(G2)={a, aa, aaa, aaaa,…}
Klasifikasi Chomsky
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
½V)*, ïaï> 02. Grammar tipe ke-1 : Context Sensitive Grammar (CSG)
Ciri : a, b Î (V½V) *, 0 < ïaï £ ïbï
½V) *, 0 < ïaï £ ïbï3. Grammar tipe ke-2 : Context Free Grammar (CFG)
Ciri : a Î V, b Î (V½V)*
, b Î (V½V)*4. Grammar tipe ke-3 : Regular Grammar (RG)
Ciri : a Î V, b Î {V, VV} atau a Î V, b Î {V, VV}
, b Î {V, VV} atau a Î V, b Î {V, VV}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.
Contoh Analisa Penentuan Type Grammar
1. Grammar G
dengan P = {S ® aB, B ® bB, B ® b}.
dengan P = {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(3).
maka G kemungkinan tipe CFG atau RG. Selanjutnya karena semua ruas kanannya terdiri dari sebuah V atau string VV maka G adalah RG(3).2. Grammar G
dengan P = {S ® Ba, B ® Bb, B ® b}.
dengan P = {S ® Ba, B ® Bb, B ® b}. 3. 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(3).
maka G kemungkinan tipe CFG atau RG. Selanjutnya karena semua ruas kanannya terdiri dari sebuah V atau string VV maka G adalah RG(3).4. Grammar G
dengan P = {S ® Ba, B ® bB, B ® b}.
dengan P = {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(2).
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(2).5. Grammar G
dengan P = {S ® aAb, B ® aB}.
dengan P = {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.
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.6. Grammar G
dengan P = {S ® aA, S ® aB, aAb ® aBCb}.
dengan P = {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.
kemungkinan tipe CSG atau UG. Selanjutnya karena semua ruas kirinya lebih pendek atau sama dengan ruas kananya maka G adalah CSG. 7. Grammar G
dengan P = {aS ® ab, SAc ® bc}.
dengan P = {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.
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 :
1. G dengan P = {1. S ® aAa, 2. A ® aAa, 3. A ® b}.
dengan P = {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)
Aa (2) Þ aba (3)
ba (3)Dari pola kedua kalimat disimpulkan : L(G) = { aba½ n ³ 1}
(G) = { aba½ n ³ 1}2. G dengan
dengan P = {1. S ® aS, 2. S ® aB, 3. B ® bC, 4. C ® aC, 5. C ® a}.
= {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
S (1)
S (1) Þ aB (2)
B (2) Þ abC (3)
bC (3) Þ abaC (4)
baC (4) ¼
Þ aba
C (4)
baC (4) Þ aba
(5)
ba (5)Dari pola kedua kalimat disimpulkan : L(G)={aba½n ³1, m³1}
(G)={aba½n ³1, m³1}3. G dengan
dengan P = {1. S ® aSBC, 2. S ® abC, 3. bB ® bb,
= {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) aabcBC (4) Þ 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}Menentukan Grammar Sebuah Bahasa
(G) = { abc½ n ³ 1}Menentukan Grammar Sebuah Bahasa1. Tentukan sebuah gramar regular untuk bahasa L = { a½ n ³ 1}
= { a½ n ³ 1}Jawab :
P(L) = {S ® aS½a}
(L) = {S ® aS½a}2. Tentukan sebuah gramar bebas konteks untuk bahasa :
L : himpunan bilangan bulat non negatif ganjil
Jawab :
Langkah kunci : digit terakhir bilangan harus ganjil.
Vt={0,1,2,..9}
Vn ={S, G,J}
P={SàHT|JT|J; TàGT|JT|J; Hà2|4|6|8; Gà0|2|4|6|8;Jà1|3|5|7|9}
P={SàGS|JS|J; Gà0|2|4|6|8;Jà1|3|5|7|9}
Buat dua buah himpunan bilangan terpisah : genap (G) dan ganjil (J)
P(L) = {S ® J½GS½JS, G ® 0½2½4½6½8, J ® 1½3½5½7½9}
(L) = {S ® J½GS½JS, G ® 0½2½4½6½8, J ® 1½3½5½7½9}3. Tentukan sebuah gramar bebas konteks untuk bahasa :
A. 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 himpunan bilangan terpisah : huruf (H) dan angka (A)
SàHT|H;TàHT|AT|H|A; Hàa|..|z; Aà0|..|9
P(L) = {S ® H½HT, T ® AT½HT½H½A,
(L) = {S ® H½HT, T ® AT½HT½H½A, H ® a½b½c½…, A ® 0½1½2½…}
4. Tentukan gramar bebas konteks untuk bahasa
L(G) = {ab½n,m ³ 1, n ¹ m}
(G) = {ab½n,m ³ 1, n ¹ m}Jawab :
Langkah kunci : sulit untuk mendefinisikan L(G) secara langsung. Jalan keluarnya adalah dengan mengingat bahwa x ¹ y berarti x > y atau x < y.
(G) secara langsung. Jalan keluarnya adalah dengan mengingat bahwa x ¹ y berarti x > y atau x < y.L = L
È L
, L ={ab½n > m ³ 1}, L = {ab½1 £ n < m}.
= LÈ L, L ={ab½n > m ³ 1}, L = {ab½1 £ n < m}.P(L) = {A ® aA½aC, C ® aCb½ab}, Q(L) = {B ® Bb½Db, D® aDb½ab}
(L) = {A ® aA½aC, C ® aCb½ab}, Q(L) = {B ® Bb½Db, D® aDb½ab}P(L) = {S® A½B, A ® aA½aC, C ® aCb½ab, B ® Bb½Db, D® aDb½ab}
(L) = {S® A½B, A ® aA½aC, C ® aCb½ab, B ® Bb½Db, D® aDb½ab}5. Tentukan sebuah gramar bebas konteks untuk bahasa :
L = bilangan bulat non negatif genap. Jika bilangan tersebut terdiri dari dua digit atau lebih maka nol tidak boleh muncul sebagai digit pertama.
= bilangan bulat non negatif genap. Jika bilangan tersebut terdiri dari dua digit atau lebih maka nol tidak boleh muncul sebagai digit pertama.Jawab :
Langkah kunci : Digit terakhir bilangan harus genap. Digit pertama tidak boleh nol. Buat tiga himpunan terpisah : bilangan genap tanpa nol (G), bilangan genap dengan nol (N), serta bilangan ganjil (J).
P(L) = {S ® N½GA½JA, A ® N½NA½JA, G® 2½4½6½8,
(L) = {S ® N½GA½JA, A ® N½NA½JA, G® 2½4½6½8, N® 0½2½4½6½8, J ® 1½3½5½7½9}
B. Mesin Pengenal Bahasa
Untuk setiap kelas bahasa Chomsky, terdapat sebuah mesin pengenal bahasa. Masing-masing mesin tersebut adalah :
Kelas Bahasa | Mesin Pengenal Bahasa |
Unrestricted Grammar (UG) | Mesin Turing (Turing Machine), TM |
Context Sensitive Grammar (CSG) | Linear Bounded Automata, LBA |
Context Free Gammar (CFG) | Pushdown Automata, PDA |
Regular Grammar, RG | Finite State Automata, FSA |
0 komentar:
Posting Komentar