Rabu, 03 Juli 2013
1. Perngertian CFG
(Context Free Grammar)
Contex Free Grammar
diperkenalkan oleh Chomsky (1956) sebagai bagian dari pembelajaran bahasa
alami. CFG / Bahasa Bebas Konteks adalah suatu metode
rekursif yang paling sederhana untuk menspesifikan aturan-aturan dalam menyusun
string dari bahasanya. CFG dapat pula menspesifikasikan bahasa-bahasa non
reguler tertentu, misalnya aturan tingkat dari bahasa pemerograman serta dari bahasa
formal lainnya
CFG ini
membantu dalam pembuatan production rule dalam pemecahan suatu
masalah yang dibuat dengan Artificial Intelligent. CFG juga berguna
dalam pengecekan string-string yang memiliki aturan tertentu (misalnya,
alamat email). Selain itu juga bisa digunakan untuk mendeskripsikan format
dokumen melalui apa yang dinamakan document type definition (DTD) yang
digunakan pada XML untuk pertukaran informasi di Web.
2. Komponen Contex Free
Grammar
Ø Sekumpulan
token yang di kenal sebagai terminal
Ø Sekumpulan
nol terminal.
Ø Sekumpulan
produksi dimana setiap produksi memiliki nol terminal disebut sebagai bagian
kiri dari produksi, sebuah panah dan seurutan token dan non terminal atau
seurutan token atau non terminal yang disebut sebagai bagian kanan dari produksi.
Ø Pemilihan
dari salah satu non terminal sebagai simbol awal.
Simbol CFG (Contex Free Grammar)
Dalam Contex Free Grammar perlu diketahui beberapa
istilah berikut yang berhubungan dengan grammar untuk bisa membedakan satu
symbol dan lainnya:
a.Simbol berikut adalah terminal :
- Huruf kecil, awal dari abjad seperti a, b, c
- Simbol operator seperti – dll.
- Angka 0,1. . . . . . .9
- Kata tercetak tebal seperti id atau if
b. Simbol beriktu adalah non terminal :
- Huruf besar, awal dari abjad seperti A, B, C
- Huruf S yang ada biasanya sebagai symbol awal.
c. Huruf besar akhir adalah abjad seperti X, Y Z
mempresentasikan simbol grammar yaitu terminal atau non terminal
d. Huruf kecil akhir dalam abjad, biasanya u, v,…z
mempresentasikan sekumpulan terminal.
e.Huruf yunani kecil, seperti α β sebagai
contoh, mempresentasikan sekumpulan umum symbol grammar. Pada umunya produksi
dapat ditulis menjadi A α, menyatakan bahwa pada produksi itu ada sebuah
non terminal a pada sisi bagian kiri dan sebuah string dari symbol grammar α
pada sisi bagian kanan.
f. Apabila tidak ada pernyataan lain, maka
bagian kiri dari produksi merupakan symbol awal.
