Grammar adalah sebagai kumpulan dari himpunan - himpunan variabel, simbol - simbol terminal, simbol awal, yang dibatasi oleh aturan - aturan produksi.
aturan produksi merupakan pusat dari grammar yang menspesifikasikan bagaimana suatu grammar melakukan transformasi suatu string atau karakter ke bentuk lainnya.
semua aturan produksi dinyatakan dalam bentuk "a->b"
(bisa dibaca a menghasilkan b, atau dibaca a menurunkan b)
a merupakan simbol - simbol pada ruas kiri aturan produksi, sedangkan b merupakan simbol ruas kanan aturan produksi.
simbol - simbol tersebut berupa simbol terminal (Vt) atau simbol NON-Terminal (Vn)/Variabel.
simbol Vn adalah simbol yang masih dapat diturunkan, biasanya identik dengan huruf besar ('A','B','C').
simbol Vt adalah simbol yang sudah tidak dapat diturunkan lagi, biasanya identik dengan huruf kecil ('a','b','c').
dengan menerapkan aturan produksi, suatu grammar bisa menghasilkan sejumlah string.
contoh aturan produksi :
dari aturan produksi di atas, menghasilkan suatu variabel a atau variabel ekspresi a+a atau a*a
Grammar (G) didenifisikan sebagai pasangan 4 tuple :
VT, VN, S, dan Q
dan dituliskan sebagai G(VT, VN, S, Q), dimana :
VT : himpunan simbol - simbol terminal (atau himpunan token - token, atau alfabet)
VN : himpunan simbol - simbol non terminal
S : 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 :
grammar tipe 0 : (Unrestricted Grammar (UG))
grammar tipe 1 : (Context Sensitive Grammar (CSG))
grammar tipe 2 : (Context Free Grammar (CFG))
grammar tipe 3 : (Regular Grammar (RG))
contoh analisa penentuan type grammar
Grammar G1 dengan Q1 = {S -> aB, B -> bB, B -> b}
jawab :
Ruas kiri semua produksinya terdiri dari sebuah VN maka G1 kemungkinan tipe CFG atau RG. selanjutnya karena semua ruas kanannya terdiri dari sebuah VT atau string VT VN maka G1 adalah RG.
Grammar G2 dengan Q2 = {S -> Ba, B -> Bb, B -> b}
jawab :
ruas kiri semua produksinya terdiri dari sebuah VN maka G2 kemungkinan tipe CFG atau RG. selanjutnya karena semua ruas kanannya terdiri dari sebuah VT atau string VNVT maka G2 adalah RG.
Grammar G3 dengan Q3 = {S -> Ba, B -> bB, B -> b}
jawab :
ruas kiri semua produksinya terdiri dari sebuah VN maka G3 kemungkinan tipe CFG atau RG. selanjutnya karena ruas kanannya mengandung string VTVN (yaitu bB) dan juga string VNVT (Ba) maka G3 bukan RG, dengan kata lain G3 adalah CFG.
Grammar G4 dengan Q4 = {S -> aAb, B -> aB}
jawab :
ruas kiri semua produksnya terdiri dari sebuah VN maka G4 kemungkinan tipe CFG atau RG. selanjutnya karena ruas kanannya mengandung string yang panjangnya lebih dari 2 (yaitu aAb) maka G4 bukan RG, dengan kata lain G4 adalah CFG.
Grammar G5 dengan Q6 = {S -> aA, S -> aB, aAb->aBCb}
jawab :
ruas kirinya mengandung string yang panjangnya lebih dari 1 (yaitu aAb) maka G5 kemungkinan tipe CSG atau UG. selanjutnya karena semua ruas kirinya lebih pendek atau sama dengan ruas kanannya maka G5 adalah CSG.
Grammar G6 dengan Q6 = {aS -> ab, SAc -> bc}. {S -> aA, S -> aB, aAb -> aBCb}
jawab :
ruas kirinya mengandung string yang panjangnya lebih dari 1 maka G6 kemungkinan tipe CSG atau UG. selanjutnya karena terdapat ruas kirinya lebih panjang dengan ruas kanannya (yaitu SAc) maka G6 adalah UG.
Komentar
Posting Komentar