® 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
: himpunan simbol-simbol
terminal (alfabet) àkamus
V
:
himpunan simbol-simbol non terminal
SÎV
: simbol awal
(atau simbol start)
P : himpunan produksi
Contoh
:
1. G1 : VT = {I, Love, Miss, You}, V
= {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 Þ 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
2.
Grammar tipe ke-1 : Context
Sensitive Grammar (CSG)
Ciri : a, b Î (V
½V
) *, 0 < ïaï £ ïbï
3.
Grammar tipe ke-2 : Context
Free Grammar (CFG)
Ciri : a Î V
, b Î (V
½V
)*
4.
Grammar tipe ke-3 : Regular
Grammar (RG)
Ciri : a Î V
, b Î {V
, V
V
} atau a Î V
, b Î {V
, V
V
}
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}.
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 V
V
maka G
adalah RG(3).
2.
Grammar G
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 V
V
maka G
adalah RG(3).
4.
Grammar G
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 V
V
(yaitu bB) dan
juga string V
V
(Ba) maka G
bukan RG,
dengan kata lain G
adalah CFG(2).
5.
Grammar G
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.
6.
Grammar G
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.
7.
Grammar G
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.
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}.
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.
G
dengan
P
= {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)
Þ a
B (2)
Þ a
bC (3)
Þ a
baC (4)
¼
Þ a
ba
C (4)
Þ a
ba
(5)
Dari pola kedua kalimat disimpulkan : L
(G
)={a
ba
½n ³1, m³1}
3.
G
dengan
P
= {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
) = { a
b
c
½ n ³ 1}Menentukan Grammar Sebuah Bahasa
1.
Tentukan sebuah gramar regular
untuk bahasa L
= { a
½ n ³ 1}
Jawab :
P
(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}
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,
H ® a½b½c½…, A ® 0½1½2½…}
4.
Tentukan gramar bebas konteks
untuk bahasa
L
(G
) = {a
b
½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.
L
= L
È L
, L
={a
b
½n > m ³ 1}, L
= {a
b
½1 £ n < m}.
P
(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}
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.
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,
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
|
by abdul hamit.
