BEBERAPA PENGERTIAN DASAR
Simbol adalah sebuah entitas abstrak (seperti halnya pengertian titik dalam geometri). Sebuah huruf atau sebuah angka adalah contoh simbol. Pada umumnya kita menggunakan huruf kecil (lower case)atau angka untuk melambngkan simbol, dan huruf kecil diakhir alphabet khususnya w,x,y,z untuk melambangkan untai (String).
String adalah deretan terbatas (finite) simbol-simbol. Sebagai contoh, jika a,b dan c adalah tiga buah simbol maka abcb adalah sebuah String yang dibangun dari ketiga simbol tersebut.
Jika w adalah sebuah String maka panjang String dinyatakan sebagai |w| dan didefinisikan sebagai cacahan (banyaknya) simbol yang menyusun String tersebut. Sebagai contoh, jika w=abcb maka |w|=4.
String hampa adalah sebuah String dengan nol buah simbol. Dinyatakan dengan simbol Ɛ (atau ˄) sehingga | Ɛ|=0. String hampa dipandang sebagai simbol hampa karena keduanya tersusun dari nol buah simbol.
Alphabet adalah himpunan hingga (finite set) simbol-simbol. Pada umumnya kita menggunakan lower case untuk melambangkan simbol, dan huruf kecil diakhir alphabet khususnya w, x, y dan z untuk melambangkan untai (String).
OPERASI DASAR STRING
Diberikan dua String : x=abc , dan y=123;
PREFIX STRING w adalah String yang dihasilkan dari String w dengan menghilangkan nol atau lebih simbol-simbol paling belakang dari String w tersebut. Contoh : abc, ab, a dan Ɛ adalah semua PREFIX(x).
PROPERPREFIK STRING w adalah String yang dihasilkan dari String w dengan menghilangkan satuatau lebih simbol-simbol paling belakang dari String w tersebut. Contoh : ab, a dan Ɛ adalah semua PROPERPREFIX(x).
POSTFIX (atau SUFIX) STRING w adalah String yang dihasilkan dari String w dengan menghilangkan nol atau lebih simbol-simbol paling depan dari String w tersebut. Contoh : abc, bc, c dan Ɛ adalah semua POSTFIX(x).
PROPERPOSTFIX (atau SUFIX) STRING w adalah String yang dihasilkan dari String w dengan menghilangkan satu atau lebih simbol-simbol paling depan dari String w tersebut. Contoh : bc, c dan Ɛ adalah semua PROPERPOSTFIX(x).
SUBSTRING STRING w adalah String yang dihasilkan dari String w dengan menghilangkan nol atau lebih simbol paling depan dan/atau simbol-simbol paling belakang dari String w tersebut. Contoh : abc, ab, bc, a, b, c dan Ɛ adalah semua SUBSTRING (x).
PROPER SUBSTRING STRING w adalah String yang dihasilkan dari String w dengan menghilangkan satu atau lebih simbol paling depan dan/atau simbol-simbol paling belakang dari String w tersebut. Contoh : ab, bc, a, b, c dan Ɛ adalah semua PROPERSUBSTRING (x).
SUBSEQUENCE STRING w adalah String yang dihasilkan dari String w dengan menghilangkan nol atau lebih simbol-simbol dari String w tersebut. Contoh : abc, ab, bc, ac, a, b, c dan Ɛ adalah semua SUBSEQUENCE (x).
PROPER SUBSEQUENCE STRING w adalah String yang dihasilkan dari String w dengan menghilangkan satu atau lebih simbol-simbol dari String w tersebut. Contoh : ab, bc, ac, a, b, c dan Ɛ adalah semua SUBSEQUENCE (x).
HEAD STRING w adalah simbol paling depan dari String w. Contoh : a adalah HEAD(x).
TAIL STRING w adalah String yang dihasilkan dari String w dengan menhilangkan HEAD tersebut. Contoh : bc adalah TAIL(x).
CONCATENATION adalah penyambungan dua buah String. Contoh : concate(xy) = xy = abc123.
ALTERNATION adalah pilihan satu diantara dua buah String. Operatornya adalah |. Contoh : alternate(xy) = x | y = abc atau 123.
KLEENE CLOSURE : x* = Ɛ | x | xx | xxx| … = Ɛ | x | x2 | x3| …
x* : menyatakan himpunan seluruh untai yang meliputi seluruh alphabet, termasuk untai kosong (Ɛ).
POSITIVE CLOSURE : x+ = x | xx | xxx |… = x | x2 | x3 | …
x+ : menyatakan himpunan seluruh untai meliputi seluruh alphabet, tidak termasuk untai kosong (Ɛ).
KONSEP DASAR
Dalam pembicaraan Grammar, anggota alphabet dinamakan simbol terminal atau token.
Kalimat adalah deretan hinggga simbol-simbol terminal.
Bahasa adalah himpunan kalimat-kalimat. Anggota bahasa bisa hingga bisa tak hingga kalimat.
Simbol berikut adalah simbol terminal :
-huruf kecil awal alphabet, misal a, b, c
– simbol operator, misal +, -, dan x
-simbol tanda baca, misal (,), dan ;
-string yang tercetak tebal, misal if, then, else
Simbol berikut adalah simbol non terminal :
-huruf besar awal alphabet, misal A, B, C
-huruf S sebagai simbol awal
-string yang tercetak miring, misal expr dan stmt
Huruf besar akhir alphabet melambangkan simbol terminal atau non terminal. Misal X, Y, Z
Huruf kecil akhir alphabet melambangkan String yang tersusun atas simbol-simbol terminal, misal x, y, z
Huruf yunani melambangkan String yang tersusun atas simbol-simbol terminal atau non terminal atau campuran keduanya, misal α, β, γ
Sebuah produksi dilambangkan sebagai α → β artinya dalam sebuah derivasi dapat dilakukan penggantian simbol α dengan simbol β
Dalam produksi berbentuk α → β. α disebut ruas kiri sedangkan β disebut ruas kanan.
Derivasi adalah proses pembentukan sebuah kalimat atau sentensial. Sebuah derivasi dilambangkan sebagai α ⇒β.
Sentensial adalah string yang tersusun atas simbol-simbol terminal atau simbol-simbol non terminal atau campuran keduanya.
Kalimat adalah string yang terssusun atas simbol-simbol terminal. Jelaslah bahwa kalimat adalah kasus khusus dari sentensial.
Pengertian terminal berasal dari kata terminate (berakhir), maksudnya derivasi berakhir jika sentensial yang dihasilkan adalah sebuah kalimat (tersusun atas simbol terminal).
Pengertian non terminal berasal dari kata not terminate (tidak/belum berhenti), derivasi tidak/belum berakhir jika sentensial yang dihasilkan mengandung simbol non terminal.
GRAMMAR DAN KLASIFIKASI CHOMSKY
Grammar G didefinisikan sebagai pasangan 4 Tuple : VT, VN, S , Q dan dituliskan sebagai G (VT, VN, S, Q), dimana :
VT : himpunan simbol terminal (atau himpunan token-token, atau alphabet)
VN : himpunan simbol-simbol non termnal
S ϵ VN : simbol awal (atau simbol start)
Q : himpunan produksi
Berdasarkan komposisi bentuk ruas kiri dan kanan produksinya (α → β), Noam Chomsky mengklasifikasikan 4 tipe grammar :
- Grammar tipe-0 : UNRESTRICTED GRAMMAR (UG)
Ciri : α, β ϵ (VT | VN)*, | α | > 0
- Grammar tipe-1 : CONTEXT SENSITIVE GRAMMAR (CSG)
Ciri : α, β ϵ (VT | VN)*, 0 < | α | ≤ | β |
- Grammar tipe-2 : CONTEXT FREE GRAMMAR (CFG)
Ciri : α ϵ VN , β ϵ (VT | VN)*
- Grammar tipe-3 : REGULLAR GRAMMAR (RG)
Ciri : α ϵ VN , β ϵ {VT , VT VN} atau α ϵ VN , β ϵ {VT , VN VT }
Mengingat ketentuan simbol-simbol maka ciri RG sering ditulis sebagai :
α ϵ VN , β ϵ {a , bC} atau α ϵ VN , β ϵ {a , Bc}
Contoh analisa penentuan type grammar
1. Grammar G1 dengan Q1 = {S→aB, B→bB, B→b}.
2. Grammar G2 dengan Q2 = {S→Ba, B→bB, B→b}.
Jawab :
- Grammar G1 dengan Q1 = {S→aB, B→bB, B→b}. Ruas kiri semua produksinya terdiri dari sebuah VN maka G1 kemungkinan type 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}. Ruas kiri semua produksinya terdiri dari sebuah VN maka G2 kemungkinan type CFG atau RG.
Selanjutnya karena semua ruas kanannya mengandung String VT VN (yaitu bB) dan juga String VN VT (Ba) maka G3 bukan RG, dengan kata lain G3 adalah CFG
Sumber :mazipanneh.wordpress-com
