Regular Grammar
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 x
- 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
campurankeduanya, misalnya : α,β dan γ
Sebuah produksi dilambangkan sebagai α→β,
artinya : dalamsebuah derivasi dapat dilakukan penggantian simbol α dengan
simbol β.
Derivasi adalah proses pembentukan
sebuah kalimat atausentensial. Sebuah derivasi dilambangkan sebagai : α ═> β
Sentensial adalah string yang tersusun
atas simbol-simbol terminalatau simbol-simbol non terminal atau campuran
keduanya.
Kalimat adalah string yang
tersusun atas simbol-simbol terminal.Kalimat adalah merupakan sentensial,
sebaliknya belum tentu..
Digunakan
pada Teori Bahasa Otomata (Mesin abstrack yang menggunakan model matematika,
tetapi menggunakan matematika yang benar-benar berbeda dengan matematika klasik
dan kalkulus). Bahasa pemrograman yang menggunakan aturan sintaktik bahasa
regular ini antara lain: Javascript & Perl. Dalam hierarki-bahasa Chomsky, grammar
regular adalah grammar paling restriktif yang dapat membangkitkan sebuahkalimat.
Dalam hierarki tersebut, grammar regular mempunyai kemampuan pembangkitan
kalimat yang sangat minimal karena:
- Sisi kiri hanya
boleh berisi sebuah nonterminal,
- Sisi kanan dalam setiap
aturan produksinya hanya boleh berisi satu nonterminal, dan posisinya hanya boleh berada di akhir atau sisi kanan rangkaian.
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, 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}.
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).
2.
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 semua ruas kanannya terdiri dari sebuah V atau
string VV maka G adalah RG(3).
3.
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 VV (yaitu bB)
dan juga string VV (Ba) maka G bukan RG, dengan kata lain G adalah CFG(2).
4.
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.
5.
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.
6.
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)
¼
Þ aAa (2)
Þ aba (3)
Dari pola kedua kalimat
disimpulkan : L(G) = { aba½ 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) Þ aS (1)
Þ aB (2)
Þ abC (3)
Þ abaC (4)
¼
Þ abaC (4)
Þ aba (5)
Dari pola kedua kalimat
disimpulkan : L(G)={aba½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) = { abc½ 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 :
B. 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) = {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.
L = 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}
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}
